Экзамен для n студентов будет проходить в длинной и узкой аудитории, таким образом, студенты будут сидеть в ряд в некотором порядке. Преподаватель подозревает, что студенты с соседними номерами (i и i + 1) в течение обучения всегда сидели рядом и подружились, и если их посадить рядом на экзамене, то они наверняка будут помогать друг другу.
Требуется выбрать максимальное количество студентов и составить такой вариант порядка размещения студентов в аудитории, что никакие два студента с соседними номерами не сидят рядом.
Выходные данные
В первую строку выведите целое число k — максимальное количество студентов, которых можно рассадить так, что никакие два студента с соседними номерами не сидят рядом.
Во вторую строку выведите k целых различных чисел a1, a2, ..., ak (1 ≤ ai ≤ n), где ai — номер студента на i-й позиции. Студенты на соседних позициях не должны иметь соседние номера. Формально, |ai - ai + 1| ≠ 1 для всех i от 1 до k - 1.
Если возможных ответов несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
11 5
abacabadaba
acaba
|
3
1 3 7
|
|
2
|
21 13
paraparallelogramgram
qolorreraglom
|
1
5
|