Multi-Heads Cup, hay viết tắt là MHC, là một cuộc thi lập trình toàn cầu dành cho những thí sinh có rất nhiều đầu. Vào năm 2023, trưởng ban giám khảo của sự kiện này, Little Cyan Fish, đã giải quyết một bài toán xác thực hóc búa bằng cách sử dụng nhiều loại dấu ngoặc.

Đó là lần đầu tiên Little Cyan Fish nhìn thấy những thí sinh có rất nhiều đầu. Và lần này, Little Cyan Fish mang đến một bài toán dấu ngoặc khác cho người bạn thân nhất của mình, người cũng có rất nhiều đầu. Little Cyan Fish có $n$ loại dấu ngoặc trong tay, và mỗi loại dấu ngoặc được chia thành dấu ngoặc mở và dấu ngoặc đóng. Để thuận tiện, chúng ta dùng $L^i$ để ký hiệu dấu ngoặc mở thuộc loại thứ $i$, và $R^i$ để ký hiệu dấu ngoặc đóng thuộc loại thứ $i$.

"Này, đừng quên nhé," Little Cyan Fish nghĩ, "Mình đã từng giới thiệu cho cậu thế nào là một dãy ngoặc cân bằng rồi!" Để đảm bảo bạn hiểu khái niệm về dãy ngoặc cân bằng, Little Cyan Fish đã chuẩn bị định nghĩa hình thức sau đây về dãy ngoặc cân bằng:

• $\varepsilon$ (xâu rỗng) là một dãy ngoặc cân bằng.
• Nếu $A$ là một dãy ngoặc cân bằng, thì $(A)$ cũng là một dãy ngoặc cân bằng.
• Nếu $A$ và $B$ là các dãy ngoặc cân bằng, thì $AB$ cũng là một dãy ngoặc cân bằng.

Ví dụ, "()", "()()" và "(())" là các dãy ngoặc cân bằng, nhưng ")(", "(" và "))" thì không.

Bây giờ, Little Cyan Fish cho bạn một dãy ngoặc $S$ có độ dài $n$, chứa $n$ loại dấu ngoặc. Thật không may, Little Cyan Fish đã quên loại dấu ngoặc ở một số vị trí, và cũng quên luôn chiều của dấu ngoặc ở những vị trí này. Ký ức về những vị trí này đã trở nên mờ nhạt và được Little Cyan Fish biểu diễn bằng ?.

Little Cyan Fish rất tò mò, với mọi $1 \le l \le r \le n$, có bao nhiêu cặp $(l, r)$ tương ứng với các xâu con $S[l \dots r]$ sao cho tồn tại một cách điền vào các dấu ? bằng một loại dấu ngoặc nào đó theo một chiều nào đó, để với mỗi $1 \le i \le n$, ta có:

• Trích xuất tất cả các dấu ngoặc thuộc loại $i$ (tức là tất cả các $L^i$ và $R^i$), dãy ngoặc thu được (chỉ chứa loại dấu ngoặc thứ $i$) là một dãy ngoặc cân bằng.

Ví dụ, nếu chúng ta dùng "()" để ký hiệu loại dấu ngoặc thứ nhất và "[]" để ký hiệu loại dấu ngoặc thứ hai, thì xâu ngoặc ([?) thỏa mãn điều kiện trên vì ta có thể thay ? bằng ]. (?)] cũng thỏa mãn điều kiện trên vì ta có thể thay ? bằng [.

Little Cyan Fish muốn bạn tính số lượng tất cả các cặp $(l, r)$ hợp lệ.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \times 10^5$), cho biết độ dài của xâu ngoặc.

Dòng tiếp theo chứa $n$ số nguyên $x_1, x_2, \dots, x_n$ ($-n \le x_i \le n$). $n$ số nguyên này mô tả thông tin của xâu ngoặc, trong đó:

• Nếu $x_i > 0$, thì vị trí thứ $i$ biểu diễn dấu ngoặc mở thuộc loại thứ $x_i$ (tức là $L^{x_i}$).
• Nếu $x_i < 0$, thì vị trí thứ $i$ biểu diễn dấu ngoặc đóng thuộc loại thứ $-x_i$ (tức là $R^{-x_i}$).
• Nếu $x_i = 0$, điều đó có nghĩa là Little Cyan Fish đã quên thông tin tại vị trí này (tức là ?).

Đảm bảo rằng tổng của $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Kết quả

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên, cho biết đáp án.

Ví dụ

Dữ liệu vào 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

Kết quả 1

1
3
3
14