Для целочисленной последовательности \(a = [a_1, a_2, \ldots, a_n]\) определим \(f(a)\) как длину самой длинной подпоследовательности\(^{\text{∗}}\) из \(a\), которая является палиндромом\(^{\text{†}}\).
Пусть \(g(a)\) обозначает число подпоследовательностей длины \(f(a)\), которые являются палиндромами. Иными словами, \(g(a)\) подсчитывает количество палиндромных подпоследовательностей в \(a\), которые имеют максимальную длину.
Для данного числа \(n\), ваша задача состоит в том, чтобы найти любую последовательность \(a\) из \(n\) целых чисел, которая удовлетворяет следующим условиям:
- \(1 \le a_i \le n\) для всех \(1 \le i \le n\).
- \(g(a) > n\)
Можно доказать, что такая последовательность всегда существует при заданных ограничениях.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — массив, удовлетворяющий условиям.
Если существует несколько решений, вы можете вывести любое из них.
Примечание
В первом примере одним из возможных решений является \(a = [1, 1, 2, 3, 1, 2]\). В этом наборе входных данных \(f(a) = 3\), поскольку самая длинная палиндромная подпоследовательность имеет длину \(3\). Существует \(7\) способов выбрать подпоследовательность длины \(3\), которая является палиндромом, как показано ниже:
- \([a_1, a_2, a_5] = [1, 1, 1]\)
- \([a_1, a_3, a_5] = [1, 2, 1]\)
- \([a_1, a_4, a_5] = [1, 3, 1]\)
- \([a_2, a_3, a_5] = [1, 2, 1]\)
- \([a_2, a_4, a_5] = [1, 3, 1]\)
- \([a_3, a_4, a_6] = [2, 3, 2]\)
- \([a_3, a_5, a_6] = [2, 1, 2]\)
\(g(a) = 7\), что больше, чем \(n = 6\). Следовательно, \(a = [1, 1, 2, 3, 1, 2]\) — это верное решение.
Во втором примере одним из возможных решений является \(a = [7, 3, 3, 7, 5, 3, 7, 7, 3]\). В этом наборе входных данных \(f(a) = 5\). Существует \(24\) способа выбрать подпоследовательность длины \(5\), которая является палиндромом. Некоторыми примерами являются \([a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]\) и \([a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]\). Следовательно, \(g(a) = 24\), что больше, чем \(n = 9\). Следовательно, \(a = [7, 3, 3, 7, 5, 3, 7, 7, 3]\) — это верное решение.
В третьем примере \(f(a) = 7\) и \(g(a) = 190\), что больше, чем \(n = 15\).