import java.util.*

fun main(args: Array<String>) {
    val rng = Random(args.contentHashCode().toLong())
    val n = args[0].toInt()
    val a = rng.nextPermutation(n)
    val b = extremal(a)
    println(n)
    println(a.map { it + 1 }.joinToString(" "))
    println(b.map { it + 1 }.joinToString(" "))
}

private fun profile(a: Array<Int>) = (0 until a.lastIndex).map { a.indexOf(it) < a.indexOf(it + 1) }

private fun extremal(a: Array<Int>): Array<Int> {
    val b = mutableListOf(0)
    val profile = profile(a)
    for (i in 1..a.lastIndex) {
        val lastPos = b.indexOf(i - 1)
        if (profile[i - 1]) {
            b.add(lastPos + 1, i)
        } else {
            b.add(lastPos, i)
        }
    }
    return b.toTypedArray()
}

private fun Random.randInt(from: Int, to: Int) = from + nextInt(to - from + 1)

private fun <T> Array<T>.swap(i: Int, j: Int) {
    val tmp = this[i]
    this[i] = this[j]
    this[j] = tmp
}

private fun Random.nextPermutation(n: Int): Array<Int> {
    val result = Array(n) { 0 }
    for (i in 1..result.lastIndex) {
        val pos = nextInt(i + 1)
        result[i] = result[pos]
        result[pos] = i
    }
    return result
}