После изучения линейной алгебры для машинного обучения Леонид решил вернуться к дискретным задачам. Одна из них ему настолько понравилась, что он решил поделиться ею с вами.

Есть массив целых ненулевых чисел $$$a_1, a_2, \ldots, a_n$$$, положительное число $$$x$$$ в массиве соответствует $$$x$$$ открывающимся скобкам, а отрицательное – $$$-x$$$ закрывающимся. Например, массив [3, -2] соответствует ((()).

Подотрезок $$$a_l, a_{l+1}, \ldots, a_r$$$, где $$$(l \le r)$$$ называется $$$хорошим$$$, если можно переупорядочить его элементы и получить массив $$$b_1, b_2, \ldots, b_{r-l+1}$$$ такой, что соответствующая ему скобочная последовательность является сбалансированной и при этом среди любых двух подряд идущих элементов массива $$$b$$$ есть хотя бы одно отрицательное число.

Для данного массива $$$a$$$ вам необходимо посчитать число его $$$хороших$$$ подотрезков.

Скобочная последовательность называется сбалансированной, если её можно превратить в правильное математическое выражение, добавив символы + и 1.