Problem Description

Every day, as part of her walk around the farm, Bessie the cow passes by her favorite pasture, where there are $N$ flowers (colorful daisies), numbered $1\ldots N$ ($1\le N\le 100$), arranged in a line. Flower $i$ has $p_i$ petals ($1\le p_i\le 1000$).

As an aspiring photographer, Bessie decides to take some photos of these flowers. Specifically, for every pair $(i,j)$ satisfying $1\le i\le j\le N$, Bessie takes a photo of all flowers from flower $i$ to flower $j$ (including $i$ and $j$).

Later, when Bessie looks at these photos, she notices that some photos contain an “average” flower: a flower that has exactly $P$ petals, where $P$ equals the average number of petals among all flowers in the photo.

How many of Bessie’s photos contain an average flower?

Input Format

The first line contains $N$. The second line contains $N$ space-separated integers $p_1\ldots p_N$.

Output Format

Output the number of photos that contain an average flower.

4
1 1 2 3

6

Hint

Sample Explanation 1

Every photo that contains only one flower is counted in the answer (there are $4$ such photos in this sample). In addition, in this sample, the photos corresponding to $(i,j)$ equal to $(1,2)$ and $(2,4)$ also contain an average flower.

Translated by ChatGPT 5