An Animal Contest 6 P3 - OAC

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type

Kyriakos Grizzly is once again hosting a party in celebration of finally hitting a OAC (one-arm chin-up)! To celebrate he has lined up N platters of food with the i^\text{th} platter containing a_i servings of delicious protein! To host a party Kyriakos will first choose a continuous subsection of platters of length K and invite K of his friends to help him finish the food. Of course since everyone loves protein, Kyriakos will only consider choosing a party with K people if and only if the total number of servings of protein can be split equally among all the K partygoers. This way no one can complain that another person ate more protein than them. Help Kyriakos determine how many different parties he can host!


1 \le N \le 10^5

1 \le a_i \le 100

Subtask 1 [30%]

1 \le a_i \le 2

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input will consist of a single integer N. The second and final line of input will contain N spaced out integers with the i^\text{th} one denoting the number of servings of protein on the i^\text{th} platter.

Output Specification

Output a single integer, the number of different parties Kyriakos can choose from.

Sample Input

6 9 4 20

Sample Output



The valid parties that Kyriakos can choose are [9, 4, 20], [6], [9], [4], [20], and [4, 20]. There are 6 possibilities.


There are no comments at the moment.