题目描述

本题为困难版。简单版和困难版之间的唯一区别在于约束条件。

如果一个字符串包含相同数量的加号和减号,我们称非空字符串平衡的。例如：字符串 +--+和 ++-+-- 是平衡的，而字符串 +--、-- 和 是不平衡的。

如果一个字符串可以通过多次使用以下操作使该字符串平衡（也可能为零），我们称字符串为有前途的：

• 将相邻的两个 - 替换为一个 +。

特别地，每个平衡字符串都是有前途的。然而，反过来则不一定成立：并不是每个有前途的字符串都是平衡的。

例如，字符串 -+--- 是有前途的，因为您可以将相邻的两个减号替换为加号，得到平衡字符串 -++-，或者得到另一个平衡字符串 -+-+。

给定的字符串 $s$ 中有多少个非空子串是有前途的？每个非空的有前途的子串都必须计算在内。

请注意，子串是字符串的连续字符序列。例如，对于字符串 +-+，它的子串有：+-、-+、+、-、+-+（字符串本身是它的子串）和一些其他的。但是下面的字符串不是它的子串：--、++、-++。

输入格式

输入的第一行包含一个整数 $(1 ≤ t ≤ 10^4)$ ——测试用例的数量。

然后是测试用例的描述。

输入数据的每个测试用例由两行组成。第一行由数字 $n (1 ≤ n ≤ 2⋅10^5)$ 组成：它是 $s$ 的长度。

测试用例的第二行包含长度为 $n$ 的字符串 $s$，它只由字符 + 和 - 组成。

保证所有测试用例中 $n$ 的值的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，输出一个数字：字符串 $s$ 的有前途的非空子串数量。每个非空有前途的子串在答案中必须计算多次，它出现了多少次在字符串 $s$ 中就计算多少次。

测试样例

5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---

2
4
2
7
4

样例说明

以下是示例中前三个测试用例的有前途的子字符串：

$s[1…2]=$+-, $s[2…3]$=-+;

$s[1…2]=$-+, $s[2…3]=$+-, $s[1…5]=$-+---, $s[3…5]=$---;

$s[1…3]=$---, $s[2…4]=$---.