Экзамен для n студентов будет проходить в длинной и узкой аудитории, таким образом, студенты будут сидеть в ряд в некотором порядке. Преподаватель подозревает, что студенты с соседними номерами (i и i + 1) в течение обучения всегда сидели рядом и подружились, и если их посадить рядом на экзамене, то они наверняка будут помогать друг другу.
Требуется выбрать максимальное количество студентов и составить такой вариант порядка размещения студентов в аудитории, что никакие два студента с соседними номерами не сидят рядом.
Выходные данные
В первую строку выведите целое число k — максимальное количество студентов, которых можно рассадить так, что никакие два студента с соседними номерами не сидят рядом.
Во вторую строку выведите k целых различных чисел a1, a2, ..., ak (1 ≤ ai ≤ n), где ai — номер студента на i-й позиции. Студенты на соседних позициях не должны иметь соседние номера. Формально, |ai - ai + 1| ≠ 1 для всех i от 1 до k - 1.
Если возможных ответов несколько, выведите любой.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
2
|
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
|
3
4 2 8
1 2
1 3
2
17 15
|
-1
|