Background

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.

Problem Description

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.”

Input Format

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

The second line contains $n$ integers — the sequence.

Output Format

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

3
8 -9 2

3

Hint

• 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