P2309 loidc, acting cute

loidc is super cute. He has been trying to win over his true love — vivym — by acting cute. After several rounds of advances, vivym-chan is about to be won over. Skilled at data structures, vivym decides to use the power of data structures to help escape.

vivym gave loidc a sequence of integers. He defines the sum of a number sequence as the sum of its elements. vivym asks loidc to find how many contiguous subarrays in the sequence have a positive sum. He thought about it for a long time but could not solve it, so he handed this tricky problem to you, who are very good at programming. He hopes you can solve it within 1 s. Otherwise, vivym will “flash over a wall and ghost-step away.”

The first line contains an integer $n$, the length of the sequence. The second line contains $n$ integers — the sequence.

Output a single integer: the number of contiguous subarrays whose sum is positive.

- For $30\%$ of the testdata: $n\leq 10^3$. - For $100\%$ of the testdata: $1 \leq n\leq 10^5$. Each element of the sequence lies between $-100\ldots 100$. Translated by ChatGPT 5