0208. Think Positive

Input file name:	positive.in
Output file name:	positive.out
Time limit:	2 s
Memory limit:	64 megabytes

It is well known, that the year on planet Eisiem has n days. Of course, some days are very good for people, while some others are just horrible. Long observations have shown for each day of the year whether this day is good for most people, or bad.

The new president of the Planet Federation wants all people to be happy. He knows that good emotions have a tendency to accumulate, just like bad ones do. The New Year however is a special event and all emotions accumulated by this moment just disappear. Therefore the president wants to change the calendar on Eisiem and choose the new first day of the year, so that the positive emotions would prevail the whole year.

More precisely, for all i from 1 to n let a_i be 1 if i-th day is good for most people and -1 if it is bad. Let s_jk be the sum of a_i for all days from the j-th day of the year to the k-th, that is:
s_jk =

Σ_i=j^k a_i, if k ≥ j
Σ_i=jⁿ a_i + Σ_i=1^k a_i, if k < j.

President wants to find such j to order the j-th day to be the first day of the year, that s_jk is positive for all k from 1 to n. Since he wants several variants to choose from, he asks you to find all such j. Since he doesn't want to get too much information at once, first of all he wants to know the number of such j. That is exactly your task.

Input file

The first line of the input file contains n – the number of days (1 ≤ n ≤ 200,000). Next line contains n integer numbers – a_i.

Output file

Output the number of different indices j, such that s_jk is positive for all k.

Examples:

positive.in	positive.out
5 1 -1 1 -1 1	1

Source: Petrozavodsk Winter 2004. Andrew Stankevich Contest 4, Friday, January 30
Author: Andrew Stankevich

Discuss       Submit a solution



Printable version