״לכל התחלה חייב להיות סוף״
עבור סדרה $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