เพื่อเฉลิมฉลองที่ไม่มีทีมใดแก้โจทย์ปัญหา "Queue Editor" ได้ในการแข่งขันรอบรองชนะเลิศ The 3rd Universal Cup เจ้าปลาสีฟ้าตัวน้อย (Little Cyan Fish) จึงได้คิดโจทย์ปัญหาใหม่ที่เกี่ยวข้องกับคิวและ... ครั้งนี้มีสแตกด้วย! เขามีลูกบอล $n$ ลูกที่มีหมายเลขกำกับตั้งแต่ $1$ ถึง $n$ ในตอนแรกลูกบอลเหล่านี้ถูกจัดเรียงอยู่ในคิว และเขายังมีสแตกว่างอีกหนึ่งอัน ในขณะที่คิวไม่ว่าง เขาจะทำตามขั้นตอนต่อไปนี้:

1. นำลูกบอลที่อยู่ด้านหน้าสุดของคิวออก ให้ $x$ เป็นหมายเลขของลูกบอลนั้น
2. ในขณะที่สแตกไม่ว่างและหมายเลขของลูกบอลที่อยู่บนสุดของสแตกมีค่ามากกว่า $x$ ให้นำลูกบอลบนสุดออกจากสแตกแล้วนำไปต่อท้ายคิว ลูกบอลจะถูกนำไปต่อท้ายคิวตามลำดับที่ถูกนำออกมา
3. นำลูกบอลที่มีหมายเลข $x$ ใส่ลงไปที่ด้านบนสุดของสแตก

สามารถพิสูจน์ได้ว่าคิวจะว่างเปล่าหลังจากทำตามขั้นตอนไปเป็นจำนวนจำกัดครั้ง จงหาจำนวนครั้งทั้งหมดที่เจ้าปลาสีฟ้าตัวน้อยนำลูกบอลใส่ลงในสแตกก่อนที่คิวจะว่าง

ข้อมูลนำเข้า

มีหลายชุดข้อมูลทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $T$ ($1 \le T$) แทนจำนวนชุดข้อมูลทดสอบ

สำหรับแต่ละชุดข้อมูลทดสอบ บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งตัวคือ $n$ ($1 \le n \le 5 \times 10^5$) แทนจำนวนลูกบอล บรรทัดที่สองประกอบด้วยจำนวนเต็ม $n$ ตัวคือ $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) แทนหมายเลขของลูกบอลในคิวเริ่มต้นจากด้านหน้าไปด้านหลัง รับประกันว่า $a_1, a_2, \ldots, a_n$ เป็นการเรียงสับเปลี่ยนของ $1, 2, \ldots, n$

รับประกันว่าผลรวมของ $n$ ในทุกชุดข้อมูลทดสอบมีค่าไม่เกิน $5 \times 10^5$

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งตัว แทนจำนวนครั้งทั้งหมดที่ลูกบอลถูกใส่ลงในสแตก

ตัวอย่าง

ข้อมูลนำเข้า 1

4
1
1
3
1 2 3
3
2 1 3
3
3 1 2

ข้อมูลส่งออก 1

1
3
5
4

ข้อมูลนำเข้า 2

2
3
2 3 1
6
1 3 4 6 2 5

ข้อมูลส่งออก 2

6
15

หมายเหตุ

ในตัวอย่างแรก ลำดับของหมายเลขลูกบอลที่ถูกใส่ลงในสแตกคือ $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ และ $(3, 1, 2, 3)$ ในสี่ชุดข้อมูลทดสอบตามลำดับ รูปภาพในโจทย์แสดงการทำงานของชุดข้อมูลทดสอบที่สามในตัวอย่างแรก

ในชุดข้อมูลทดสอบแรกของตัวอย่างที่สอง ลำดับของหมายเลขที่ถูกใส่ลงในสแตกคือ $(2, 3, 1, 3, 2, 3)$ ดังนั้นคำตอบคือ $6$ ในชุดข้อมูลทดสอบที่สองของตัวอย่างที่สอง ลำดับคือ $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$ ดังนั้นคำตอบคือ $15$