Это сложная версия задачи F. Единственное различие между простой и сложной версиями заключается в ограничениях.
Будем называть непустую строку сбалансированной, если она содержит одинаковое количество знаков плюс и минус. Например: строки «+--+» и «++-+--» являются сбалансированными, а строки «+--», «--» и «» не являются сбалансированными.
Будем называть строку перспективной, если строку можно сделать сбалансированной при помощи нескольких(возможно нуля) применений следующей операции:
- заменим два соседних знака минуса на один знак плюс.
В частности, всякая сбалансированная строка является перспективной. Однако обратное неверно: не всякая перспективная строка — сбалансирована.
Например: строка «-+---» является перспективной, так как можно заменить два соседних минуса на плюс и получить сбалансированную строку «-++-», либо получить другую сбалансированную строку «-+-+».
Сколько непустых подстрок данной строки \(s\) являются перспективными? Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке \(s\).
Напомним, что подстрока — это последовательность подряд идущих символов строки. Например, для строки «+-+» её подстроками являются строки «+-», «-+», «+», «+-+» (строка является подстрокой самой себя) и некоторые другие. Но следующие строки её подстроками не являются: «--», «++», «-++».
Выходные данные
Для каждого набора входных данных выведите единственное число — количество непустых перспективных подстрок строки \(s\). Каждая непустая перспективная подстрока должна быть учтена в ответе столько раз, сколько раз она встречается в строке \(s\).