Sunny and Rock have successfully conquered the linear world and obtained a treasure: an array $A$ consisting of $N$ integers. The $i$-th element of the array is denoted by $A_i$. They now want to split the array into two consecutive parts by selecting an index $j$, where $1 \le j < N$. Sunny will take the first part of the array, containing $A_1, A_2, ..., A_j$, while Rock will take the remaining portion. For the split to be fair, the two parts must have equal ranges.

The range of a set of integers is defined as the difference between its maximum and minimum values.

Your task is to help Sunny and Rock determine how many values of $j$ result in a fair partition.

Input

The first line contains a single integer $N$.
The second line contains $N$ integers, where the $i$-th integer is $A_i$.

Output

Output a single integer, representing the number of values of $j$ that lead to a fair partition.

Constraints

For all test cases: $2 \le N \le 10^5$, $1 \le A_i \le 10^9$
Subtask 1 (30%): $2 \le N \le 1000$
Subtask 2 (70%): No additional constraints