Вам дан массив \(a\) из \(n\) целых положительных чисел.
Пусть \(\text{LIS}(a)\) обозначает длину самой длинной строго возрастающей подпоследовательности \(a\). Например,
- \(\text{LIS}([2, \underline{1}, 1, \underline{3}])\) = \(2\).
- \(\text{LIS}([\underline{3}, \underline{5}, \underline{10}, \underline{20}])\) = \(4\).
- \(\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])\) = \(3\).
Мы определяем массив \(a'\) как массив, полученный после разворота массива \(a\), т.е. \(a' = [a_n, a_{n-1}, \ldots , a_1]\).
Красота массива \(a\) определяется как \(min(\text{LIS}(a),\text{LIS}(a'))\).
Ваша задача — определить максимально возможную красоту массива \(a\), если вы можете произвольно переставить местами элементы массива \(a\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимально возможную красоту \(a\) после перестановки его элементов произвольным способом.
Примечание
В первом наборе входных данных \(a\) = \([6, 6, 6]\) и \(a'\) = \([6, 6, 6]\). \(\text{LIS}(a) = \text{LIS}(a')\) = \(1\). Следовательно, красота равна \(min(1, 1) = 1\).
Во втором наборе входных данных \(a\) может быть перестроено в \([2, 5, 4, 5, 4, 2]\). Тогда \(a'\) = \([2, 4, 5, 4, 5, 2]\). \(\text{LIS}(a) = \text{LIS}(a') = 3\). Следовательно, красота равна \(3\), и можно показать, что это максимально возможная красота.
В третьем наборе входных данных \(a\) может быть перестроено в \([1, 2, 3, 2]\). Тогда \(a'\) = \([2, 3, 2, 1]\). \(\text{LIS}(a) = 3\), \(\text{LIS}(a') = 2\). Следовательно, красота равна \(min(3, 2) = 2\) и можно показать, что \(2\) — это максимально возможная красота.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
6 6 6
6
2 5 4 5 2 4
4
1 3 2 2
|
1
3
2
|