After studying linear algebra for machine learning, Leonid decided to return to discrete problems. One of them he liked so much that he decided to share it with you.

There is an array of non-zero integers $$$a_1, a_2, \ldots, a_n$$$, where a positive number $$$x$$$ in the array corresponds to $$$x$$$ opening brackets, and a negative number corresponds to $$$-x$$$ closing brackets. For example, the array [3, -2] corresponds to ((()).

A subarray $$$a_l, a_{l+1}, \ldots, a_r$$$, where $$$(l \le r)$$$ is called $$$good$$$ if its elements can be rearranged to form an array $$$b_1, b_2, \ldots, b_{r-l+1}$$$ such that the corresponding bracket sequence is balanced and there is at least one negative number among any two consecutive elements of the array $$$b$$$.

For the given array $$$a$$$, you need to count the number of its $$$good$$$ subarrays.

A bracket sequence is called balanced if it can be turned into a correct mathematical expression by adding the symbols + and 1.