有一个长度为$n$的序列，现在我们想把它切割成三段(每一段都是连续的），使得每一段的元素总和都相同，请问有多少种不同的切割方法

输入描述

第一行给出一个数$n$，($1\le n \le 10^5$)

第二行给出序列$a_1$，$a_2$，$a_3$，...，$a_n$，($|a_i|\le 10^5$)

输出描述

输出一个数表示有多少种不同的切割方法

样例输入

4
1 2 3 3

样例输出

1

样例解释

可以将它分成第一组$1$，$2$，第二组$3$，第三组$3$