كأس الرؤوس المتعددة (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