Three Sections

Problem Description

You are given a sequence of length $n$. We want to cut it into three contiguous segments so that each segment has the same total sum. Count the number of different ways to do this.

Input Format

The first line gives $n$ ($1 \leq n \leq 10^5$).

The second line gives $a_1, a_2, a_3, \dots, a_n$ ($|a_i| \leq 10^5$).

Output Format

Output the number of different ways to cut the sequence.

Sample Input

4
1 2 3 3

Sample Output

1

Sample Explanation

We can split it into the first group $\{1, 2\}$, the second group $\{3\}$, and the third group $\{3\}$.