CF1660F2 Promising String (hard version)

如果一个非空字符串包含了相同个数的加号与减号，我们把它称之为一个平衡字符串。 比如`+--+`,`++-+--`都是平衡的，而字符串`+--`,`--`,` `都不是平衡的。 如果一个字符串可以通过几个（可以是$0$个）操作而变得平衡，我们称它是有希望的。具体操作为： 把两个相邻的减号替换为一个加号 显然所有的平衡字符串都是有希望的，不过不是所有有希望的字符串都是平衡的。比如字符串`-+---`是一个有希望的字符串。因为 你可以把两个相邻的减号替换为一个加号从而达到一个平衡字符串`-++-`或`-+-+` 对于一个给定的字符串$s$,你要求出有它多少个非空子串是有希望的。如果一个子串在$s$中出现了多次，我们也要计算多次

第一行输入一个正整数$t$($1 \leq t \leq 10^4$)，代表有多少个测试数据 对于每一个测试数据，输入两行。 第一行一个正整数$n$($1 \leq n \leq 2 \times 10^5$),表示字符串$s$的长度 第二行输入一个字符串$s$,仅由`+`,`-`构成 保证对于所有测试数据，$n$的和不会超过$2 \times 10^5$

对于每一个输出数据，输出它多少个非空子串是有希望的。

The following are the promising substrings for the first three test cases in the example: 1. $ s[1 \dots 2] $ ="+-", $ s[2 \dots 3] $ ="-+"; 2. $ s[1 \dots 2] $ ="-+", $ s[2 \dots 3] $ ="+-", $ s[1 \dots 5] $ ="-+---", $ s[3 \dots 5] $ ="---"; 3. $ s[1 \dots 3] $ ="---", $ s[2 \dots 4] $ ="---".