F. Красивая последовательность возвращается
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем последовательность целых чисел красивой, если выполняются следующие условия:

  • для каждого элемента, кроме первого, существует элемент слева, который меньше его;
  • для каждого элемента, кроме последнего, существует элемент справа, который больше его;

Например, $$$[1, 2]$$$, $$$[42]$$$, $$$[1, 4, 2, 4, 7]$$$ и $$$[1, 2, 4, 8]$$$ являются красивыми, но $$$[2, 2, 4]$$$ и $$$[1, 3, 5, 3]$$$ — нет.

Напомним, что подпоследовательность — это последовательность, которую можно получить из другой последовательности, удалив некоторые элементы (возможно, ни одного), не изменяя порядок оставшихся элементов.

Вам дан целочисленный массив $$$a$$$ размером $$$n$$$. Найдите самую длинную красивую подпоследовательность массива $$$a$$$ и выведите ее длину.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ независимых наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — длину массива $$$a$$$.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) – массив $$$a$$$.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам не превышает $$$5 \cdot 10^5$$$.

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

Для каждого набора выведите одно целое число — длину самой длинной красивой подпоследовательности массива $$$a$$$.

Пример
Входные данные
5
1
42
5
1 2 3 4 5
6
6 5 4 3 2 1
7
1 1 3 4 2 3 4
6
2 3 1 1 2 4
Выходные данные
1
5
1
5
3