“ทุกจุดเริ่มต้นย่อมมีจุดสิ้นสุด”
สำหรับลำดับ $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