Але досталась сложная задача. К сожалению, она слишком занята баллотированием в студенческий совет. Пожалуйста, решите эту задачу за неё.
Дано целое число \(n\). Постройте перестановку \(p\) целых чисел \(1, 2, \ldots, n\), которая максимизирует значение \(k\) (которое изначально равно \(0\)) после следующего процесса.
Выполняется \(n\) операций, на \(i\)-й операции (\(i=1, 2, \dots, n\)):
- Если \(i\) нечетно, то \(k=k\,\&\,p_i\), где \(\&\) обозначает операцию побитового И.
- Если \(i\) четно, то \(k=k\,|\,p_i\), где \(|\) обозначает операцию побитового ИЛИ.
Выходные данные
Для каждого набора входных данных выведите максимальное значение \(k\) в первой строке и перестановку \(p_1, p_2,\ldots, p_n\) во второй строке.
Если подходящих перестановок несколько, выведите любую из них.
Примечание
В первом наборе входных данных максимальное значение \(k\) получается следующим образом:
Изначально \(k = 0\).
- На \(1\)-й операции: \(1\) нечётно, поэтому Аля задает \(k\) равным \(k\&p_1 = 0\&2 = 0\).
- На \(2\)-й операции: \(2\) чётно, поэтому Аля задает \(k\) равным \(k|p_2 = 0|1 = 1\).
- На \(3\)-й операции: \(3\) нечетно, поэтому Аля задает \(k\) равным \(k\&p_3 = 1\&3 = 1\).
- На \(4\)-й операции: \(4\) четно, поэтому Аля задает \(k\) равным \(k|p_4 = 1|4 = 5\).
- На \(5\)-й операции: \(5\) нечетно, поэтому Аля задает \(k\) равным \(k\&p_5 = 5\&5 = 5\).
Итоговое значение \(k\) равно \(5\). Можно показать, что итоговое значение \(k\) не может превышать \(5\) для всех перестановок длины \(5\). Другой корректный ответ — \([2, 3, 1, 4, 5]\).
Для второго набора входных данных максимальное значение \(k\) равно \(7\). Можно показать, что итоговое значение \(k\) не может быть больше \(7\) для всех перестановок длины \(6\). Другие корректные ответы: \([2, 4, 1, 6, 3, 5]\) и \([5, 2, 6, 1, 3, 4]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
6
7
8
9
10
|
5
2 1 3 4 5
7
1 2 4 6 5 3
7
2 4 5 1 3 6 7
15
2 4 5 1 3 6 7 8
9
2 4 5 6 7 1 3 8 9
15
1 2 3 4 5 6 8 10 9 7
|