H. Премия Тьюринга
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алан Тьюринг стоит на бесконечной в обе стороны ленте, разделённой на ячейки.

Ячейки пронумерованы слева направо подряд идущими целыми числами, а Алан изначально стоит в ячейке $$$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$$$.

Помогите Алану и определите, каков максимальный возможный размер его премии, если он будет действовать оптимально.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.

Каждый набор входных данных задан на двух строках. Первая строка набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 15\,000$$$) — длину перестановки, предоставленной Алану.

Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы перестановки.

Гарантируется, что перестановка была выбрана случайно равновероятно среди всех перестановок соответствующей длины.

Сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$15\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальный возможный размер премии Тьюринга.

Взломы в этой задаче запрещены.

Пример
Входные данные
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
Примечание

Наибольшая возрастающая подпоследовательность последовательности $$$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]$$$.