F2. Перспективные подстроки (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи F. Единственное различие между простой и сложной версиями заключается в ограничениях.

Будем называть непустую строку сбалансированной, если она содержит одинаковое количество знаков плюс и минус. Например: строки «+--+» и «++-+--» являются сбалансированными, а строки «+--», «--» и «» не являются сбалансированными.

Будем называть строку перспективной, если строку можно сделать сбалансированной при помощи нескольких(возможно нуля) применений следующей операции:

  • заменим два соседних знака минуса на один знак плюс.

В частности, всякая сбалансированная строка является перспективной. Однако обратное неверно: не всякая перспективная строка — сбалансирована.

Например: строка «-+---» является перспективной, так как можно заменить два соседних минуса на плюс и получить сбалансированную строку «-++-», либо получить другую сбалансированную строку «-+-+».

Сколько непустых подстрок данной строки $$$s$$$ являются перспективными? Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке $$$s$$$.

Напомним, что подстрока — это последовательность подряд идущих символов строки. Например, для строки «+-+» её подстроками являются строки «+-», «-+», «+», «+-+» (строка является подстрокой самой себя) и некоторые другие. Но следующие строки её подстроками не являются: «--», «++», «-++».

Входные данные

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Каждый набор входных данных состоит из двух строк. В первой строке дано число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — длина строки $$$s$$$.

Во второй строке набора дана строка $$$s$$$ длины $$$n$$$, состоящая только из знаков «+» и «-».

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное число — количество непустых перспективных подстрок строки $$$s$$$. Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке $$$s$$$.

Пример
Входные данные
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---
Выходные данные
2
4
2
7
4
Примечание

Ниже перечислены перспективные подстроки для первых трёх наборов входных данных примера:

  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]$$$=«---».