«لكل بداية لا بد من نهاية»
بالنسبة للمتتالية $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