Multi-Heads Cup หรือเรียกสั้นๆ ว่า MHC คือการแข่งขันเขียนโปรแกรมระดับโลกที่จัดขึ้นสำหรับผู้เข้าแข่งขันที่มีหลายหัวมากๆ ในปี 2023 หัวหน้ากรรมการของการแข่งขันนี้คือ Little Cyan Fish ได้แก้ปัญหาการยืนยันตัวตนสุดหินโดยใช้วงเล็บหลายชนิด

นั่นเป็นครั้งแรกที่ Little Cyan Fish ได้เห็นผู้เข้าแข่งขันที่มีหลายหัวมากๆ และในครั้งนี้ Little Cyan Fish ก็ได้นำโจทย์ปัญหาวงเล็บอีกข้อมาฝากเพื่อนสนิทของเขาที่มีหลายหัวมากๆ เช่นกัน Little Cyan Fish มีวงเล็บ $n$ ชนิดอยู่ในมือ และวงเล็บแต่ละชนิดแบ่งออกเป็นวงเล็บเปิดและวงเล็บปิด เพื่อความสะดวก เราใช้ $L^i$ แทนวงเล็บเปิดชนิดที่ $i$ และใช้ $R^i$ แทนวงเล็บปิดชนิดที่ $i$

"เฮ้ อย่าลืมสิ" Little Cyan Fish คิดในใจ "ฉันเคยแนะนำให้เธอรู้จักแล้วนะว่าลำดับวงเล็บที่สมดุลคืออะไร!" เพื่อให้แน่ใจว่าคุณเข้าใจแนวคิดของลำดับวงเล็บที่สมดุล Little Cyan Fish จึงได้เตรียมนิยามอย่างเป็นทางการของลำดับวงเล็บที่สมดุลไว้ดังนี้:

• $\varepsilon$ (สตริงว่าง) เป็นลำดับวงเล็บที่สมดุล
• ถ้า $A$ เป็นลำดับวงเล็บที่สมดุล แล้ว $(A)$ ก็เป็นลำดับวงเล็บที่สมดุลเช่นกัน
• ถ้า $A$ และ $B$ เป็นลำดับวงเล็บที่สมดุล แล้ว $AB$ ก็เป็นลำดับวงเล็บที่สมดุลเช่นกัน

ตัวอย่างเช่น "()", "()()" และ "(())" เป็นลำดับวงเล็บที่สมดุล แต่ ")(", "(" และ "))" ไม่ใช่

ตอนนี้ Little Cyan Fish ให้ลำดับวงเล็บ $S$ ที่มีความยาว $n$ ซึ่งประกอบด้วยวงเล็บ $n$ ชนิดแก่คุณ น่าเสียดายที่ Little Cyan Fish ลืมชนิดของวงเล็บในบางตำแหน่ง และยังลืมทิศทางของวงเล็บในตำแหน่งเหล่านั้นด้วย ความทรงจำเกี่ยวกับตำแหน่งเหล่านี้พร่ามัวไปแล้วและถูกแทนด้วย ? โดย Little Cyan Fish

Little Cyan Fish สงสัยมากว่า สำหรับทุกๆ $1 \le l \le r \le n$ มีคู่ $(l, r)$ กี่คู่ที่สอดคล้องกับสตริงย่อย $S[l \dots r]$ ซึ่งมีวิธีเติม ? ด้วยวงเล็บชนิดใดชนิดหนึ่งในทิศทางใดทิศทางหนึ่ง ที่ทำให้สำหรับแต่ละ $1 \le i \le n$ เรามี:

• เมื่อดึงวงเล็บชนิดที่ $i$ ทั้งหมดออกมา (กล่าวคือ $L^i$ และ $R^i$ ทั้งหมด) ลำดับวงเล็บที่ได้ (ซึ่งประกอบด้วยวงเล็บชนิดที่ $i$ เท่านั้น) จะเป็นลำดับวงเล็บที่สมดุล

ตัวอย่างเช่น หากเราใช้ "()" แทนวงเล็บชนิดที่หนึ่ง และใช้ "[]" แทนวงเล็บชนิดที่สอง สตริงวงเล็บ ([?) จะสอดคล้องกับเงื่อนไขข้างต้น เพราะเราสามารถแทนที่ ? ด้วย ] ได้ และ (?)] ก็สอดคล้องกับเงื่อนไขข้างต้นเช่นกัน เพราะเราสามารถแทนที่ ? ด้วย [ ได้

Little Cyan Fish ต้องการให้คุณคำนวณจำนวนคู่ $(l, r)$ ที่ถูกต้องทั้งหมด

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

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

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

บรรทัดถัดไปประกอบด้วยจำนวนเต็ม $n$ ตัว คือ $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$) จำนวนเต็ม $n$ ตัวนี้อธิบายข้อมูลของสตริงวงเล็บ โดยที่:

• ถ้า $x_i > 0$ ตำแหน่งที่ $i$ จะแทนวงเล็บเปิดชนิดที่ $x_i$ (กล่าวคือ $L^{x_i}$)
• ถ้า $x_i < 0$ ตำแหน่งที่ $i$ จะแทนวงเล็บปิดชนิดที่ $-x_i$ (กล่าวคือ $R^{-x_i}$)
• ถ้า $x_i = 0$ หมายความว่า Little Cyan Fish ลืมข้อมูลที่ตำแหน่งนี้ไปแล้ว (กล่าวคือ ?)

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

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

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

ตัวอย่าง

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

4
4
1 2 -1 -2
4
1 0 -2 0
6
1 2 3 -3 -2 -1
8
1 0 0 3 0 0 0 -2

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

1
3
3
14