Алан Тьюринг стоит на бесконечной в обе стороны ленте, разделённой на ячейки.
Ячейки пронумерованы слева направо подряд идущими целыми числами, а Алан изначально стоит в ячейке \(0\). Слева от любой ячейки \(x\) находится ячейка \(x - 1\), а справа — ячейка \(x + 1\).
Каждая ячейка может либо содержать целое число, либо быть пустой. Изначально все ячейки пусты.
Алану выдали перестановку \(a_1, a_2, \ldots, a_n\) чисел от \(1\) до \(n\), выбранную случайно равновероятно среди всех перестановок длины \(n\).
В момент времени \(1\) в ячейку \(0\), в которой находится Алан, записывается число \(a_1\).
В каждый момент времени \(i\) до \(2\) до \(n\) включительно происходит следующее. Сначала Алан принимает решение, остаться ли ему в той же ячейке, где он сейчас находится, сдвинуться на соседнюю ячейку слева, или же сдвинуться на соседнюю ячейку справа. После этого в ту ячейку, где находится Алан, записывается число \(a_i\). Если ячейка уже содержала некоторое число, старое число перезаписывается и больше не играет роли.
После того, как в момент времени \(n\) в некоторую ячейку будет записано число \(a_n\), сформируется последовательность \(b\) из всех чисел, записанных в ячейках, слева направо. Пустые ячейки игнорируются.
Премия Тьюринга будет равна длине наибольшей возрастающей подпоследовательности последовательности \(b\).
Помогите Алану и определите, каков максимальный возможный размер его премии, если он будет действовать оптимально.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальный возможный размер премии Тьюринга.
Взломы в этой задаче запрещены.
Примечание
Наибольшая возрастающая подпоследовательность последовательности \(b\) — это самая длинная возрастающая последовательность, которую можно получить удалением нескольких (возможно, ни одного или всех) элементов из \(b\).
В первом наборе входных данных Алан может принять решение только в момент времени \(2\). Если Алан останется в ячейке \(0\), последовательность \(b\) будет равна \([2]\). Если Алан сдвинется влево, в ячейку \(-1\), последовательность \(b\) будет равна \([2, 1]\). Если Алан сдвинется вправо, в ячейку \(1\), последовательность \(b\) будет равна \([1, 2]\). Только в последнем случае длина наибольшей возрастающей подпоследовательности в \(b\) равна \(2\), следовательно, ответ равен \(2\).
Во втором наборе входных данных одна из оптимальных последовательностей действий такова: сдвинуться влево в моменты времени \(2\) и \(3\), и сдвинуться вправо в момент времени \(4\). Тогда последовательность \(b\) будет равна \([2, 3, 4]\), длина её наибольшей возрастающей подпоследовательности — \(3\).
В третьем наборе входных данных один из оптимальных способов — всё время сдвигаться влево. Тогда последовательность \(b\) будет равна \([2, 1, 4, 7, 5, 6, 3]\), длина её наибольшей возрастающей подпоследовательности — \(4\).
В четвёртом наборе входных данных один из оптимальных способов — четырежды сдвинуться вправо, далее один раз сдвинуться влево, и один раз остаться на месте. Последовательность \(b\) будет равна \([5, 2, 3, 4, 6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 2
4
4 1 2 3
7
3 6 5 7 4 1 2
7
5 2 3 7 6 1 4
|
2
3
4
4
|