Three Little Pigs

Three little pigs want to build houses along the river. There are many apple trees along the river. Each tree has its own quality level which affects the overall quality of the garden. A positive value means that the tree is good. A zero or negative value means that the tree is bad.

The little pigs want to divide the territory in such a way that each of them gets gardens of the same quality. They need your help to determine how many ways they can divide the territory.

Input

The first line of input contains an integer N$,$ representing the number of apple trees along the river.

The second line of input contains N space seperated integers as a$1,$ a$2...$ an$,$ where a represents the quality of ith tree.

Output