«У кожного початку має бути кінець»
Для послідовності $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