Экзамен для n студентов будет проходить в длинной и узкой аудитории, таким образом, студенты будут сидеть в ряд в некотором порядке. Преподаватель подозревает, что студенты с соседними номерами (i и i + 1) в течение обучения всегда сидели рядом и подружились, и если их посадить рядом на экзамене, то они наверняка будут помогать друг другу.
Требуется выбрать максимальное количество студентов и составить такой вариант порядка размещения студентов в аудитории, что никакие два студента с соседними номерами не сидят рядом.
В единственной строке задано целое число n (1 ≤ n ≤ 5000) — количество студентов на экзамене.
В первую строку выведите целое число k — максимальное количество студентов, которых можно рассадить так, что никакие два студента с соседними номерами не сидят рядом.
Во вторую строку выведите k целых различных чисел a1, a2, ..., ak (1 ≤ ai ≤ n), где ai — номер студента на i-й позиции. Студенты на соседних позициях не должны иметь соседние номера. Формально, |ai - ai + 1| ≠ 1 для всех i от 1 до k - 1.
Если возможных ответов несколько, выведите любой.
6 5 8 4 6 3 12 1 2 1 3 4 2 2 5 6 3 6 7 4 2 5 3 11
6
7 10 14 7 12 4 50 1 1 2 2 3 2 4 5 1 6 5 1 7 6 7 3 4 8 8 10
0
3 4 2 8 1 2 1 3 2 17 15
-1
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач