题目描述

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。请计算把整个数组分成三个非空连续部分，并使三个部分元素和都相等的方案数。

更形式化地，统计满足 $2\le i\le j\le n-1$ 的下标对 $(i,j)$ 的数量，使得

三个部分分别为 $[1,i-1]$、$[i,j]$ 和 $[j+1,n]$。

输入格式

第一行一个整数 $n$（$1\le n\le5\cdot10^5$）。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$|a_i|\le10^9$）。

输出格式

输出一个整数，表示将数组分为三个元素和相等的连续部分的方案数。

样例

样例 1

输入：

5
1 2 3 0 3

输出：

2

样例 2

输入：

4
0 1 -1 0

输出：

1

样例 3

输入：

2
4 1

输出：

0