«У каждого начала должен быть конец»
Для последовательности $A = (a_1, a_2, \dots, a_m)$ определим:
- длину наибольшей строго возрастающей подпоследовательности: $$\text{LIS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} < a_{i_2} < \dots < a_{i_k}\}$$
- длину наибольшей строго убывающей подпоследовательности: $$\text{LDS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} > a_{i_2} > \dots > a_{i_k}\}$$
Для любой последовательности $A$ определим $f(A)$ как наибольшее целое число $k$, удовлетворяющее следующим условиям:
Существуют $k$ вещественных чисел $x_1, x_2, \dots, x_k$. После их последовательного дописывания в конец $A$ мы получаем новую последовательность $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, для которой выполняются следующие условия:
- Все элементы последовательности $B$ попарно различны;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Теперь дана перестановка $P = (P_1, P_2, \dots, P_n)$ длины $n$. Для каждого префикса $P^{(i)} = (P_1, P_2, \dots, P_i)$ вам необходимо вычислить $f(P^{(i)})$ и вывести все ответы.
«Однажды я вернусь к тебе»
Входные данные
Первая строка содержит целое число $T$ ($1 \le T \le 10^5$), обозначающее количество наборов входных данных.
Для каждого набора входных данных:
- Первая строка содержит целое число $n$ ($1 \le n \le 2 \cdot 10^5$);
- Вторая строка содержит $n$ целых чисел $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), представляющих перестановку длины $n$.
Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $2 \cdot 10^5$.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую $n$ целых чисел — ответы.
Примеры
Входные данные 1
5 2 1 2 3 1 3 2 4 3 4 1 2 5 2 5 1 3 4 6 3 6 2 1 4 5
Выходные данные 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2