You've got array a[1], a[2], ..., a[n], consisting of n integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same. 

More formally, you need to find the number of such pairs of indices i, j (2 ≤ i ≤ j ≤ n - 1), that $\sum_{k = 1}^{i - 1} a_{k} = \sum_{k = i}^{j} a_{k} = \sum_{k = j + 1}^{n} a_{k}$.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 5·10^5), showing how many numbers are in the array. The second line contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤  10^9) — the elements of array a.


-----Output-----

Print a single integer — the number of ways to split the array into three parts with the same sum.


-----Examples-----
Input
5
1 2 3 0 3

Output
2

Input
4
0 1 -1 0

Output
1

Input
2
4 1

Output
0

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Contest 266 Div 2 Problem C

Author  : chaotic_iak
Language: Python 3.3.4
"""

def main():
    n, = read()
    a = read()
    s = sum(a)
    if s%3:
        print(0)
        return
    s //= 3
    t = 0
    ct = 0
    res = 0
    for i in range(n-1):
        t += a[i]
        if t == 2*s:
            res += ct
        if t == s:
            ct += 1
    print(res)

################################### NON-SOLUTION STUFF BELOW

def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

import sys

n = int(sys.stdin.readline())
a = [int(x) for x in sys.stdin.readline().split()]

s = [a[0]]
sucet = a[0]
for i in range(1, len(a)):
    s.append(s[-1] + a[i])
    sucet += a[i]

if sucet % 3 != 0:
    print(0)
else:
    moznosti = 0
    dvoj = 2*(sucet//3)
    kdedvoj = [(0, 1)[s[0] == dvoj]]
    for i in range(1, len(s)):
        kdedvoj.append(kdedvoj[-1] + (0, 1)[s[i] == dvoj])
    if sucet == 0:
        if kdedvoj[-1] - 2 < 1: print(0)
        elif kdedvoj[-1] - 2 == 1: print(1)
        else: print((kdedvoj[-1]**2 - 3*kdedvoj[-1] + 2)//2)
    else:
        j = n
        for i in range(len(a)):
            if s[i] == sucet//3:
                j = i
                break
        k = -1
        for i in range(len(a)-1, -1, -1):
            if s[i] == sucet:
                k = i
                break
        for i in range(j, k):
            if s[i] == sucet//3:
                moznosti += (kdedvoj[-1] - kdedvoj[i]);
        print(moznosti)

n=int(input())

a=list(map(int, input().split()))

s0=sum(a)
if s0%3!=0:
    print(0)
else:
    s=s0//3
    d=[0 for i in range(n)]
    temp=a[-1]
    d[-1]= 1 if temp==s else 0
    for i in range(2, n+1):
        temp+=a[-i]
        d[-i]=d[-i+1] + (1 if temp==s else 0)
    k=0
    temp=0
    for i in range(n-2):
        temp+=a[i]
        if temp==s:
            k+=d[i+2]
    print(k)


n, a = int(input()), list(map(int, input().split()))
sums, s = [[0, 0]] + [0] * n, sum(a)
for i in range(n):
    sums[i + 1] = [sums[i][0] + a[i], sums[i][1] + int(i != n - 1 and (sums[i][0] + a[i]) * 3 == s * 2)]
print(0 if s % 3 else sum(sums[-1][1] - sums[i][1] for i in range(1, n) if sums[i][0] * 3 == s))


n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in a[1:]:
    b.append(b[-1] + i)
d = [a[-1]]
for i in a[:-1][::-1]:
    d.append(d[-1] + i)
d = d[::-1]
c = [0] * n
s = b[n - 1]

if b[0] * 3 == s:
    c[0] = 1
for i in range(1, n):
    if b[i] * 3 == s:
        c[i] = c[i - 1] + 1
    else:
        c[i] = c[i - 1]

ans = 0
for i in range(2, n):
    if d[i] * 3 == s:
        ans = ans + c[i - 2]

print(ans)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    
    if s % 3 != 0 or len(a) < 3:
        print(0)
        return

    _s = s // 3
    sums = [0] * (n+1)
    ss = 0
    for i in range(n-1, 1, -1):
        ss += a[i]
        sums[i] = sums[i+1] + int(ss == _s)

    res = 0
    ss = 0 
    for i in range(n-2):
        ss += a[i]
        if ss == _s:
            res += sums[i+2]
    print(res)
            

def __starting_point():
    main()


__starting_point()

from array import array
from bisect import bisect_right as bisect

def solve(nums):
    nums = array('l', nums)

    full_sum = sum(nums)
    third, modulo = divmod(full_sum, 3)
    two_thirds = third * 2

    if modulo:
        return 0

    a = array('l')
    b = array('l')

    len_nums_m2 = len(nums) - 2
    len_nums_m1 = len(nums) - 1

    accum = 0
    for i, n in enumerate(nums, 1):
        accum += n
        if accum == third and i <= len_nums_m2:
            a.append(i)
        if accum == two_thirds and 1 < i <= len_nums_m1:
            b.append(i)

    len_b = len(b)
    result = 0
    for n in a:
        subsize_b = len_b - bisect(b, n)
        result += subsize_b

    return result


def __starting_point():
    _ = int(input())
    nums = list(map(int, input().split()))
    answer = solve(nums)
    print(answer)

__starting_point()

from array import array
from bisect import bisect_right as bisect

def solve(nums):
    nums = array('l', nums)

    full_sum = sum(nums)
    third, modulo = divmod(full_sum, 3)
    two_thirds = third * 2

    if modulo:
        return 0

    a = array('l')
    b = array('l')

    len_nums_m2 = len(nums) - 2
    len_nums_m1 = len(nums) - 1

    accum = 0
    for i, n in enumerate(nums, 1):
        accum += n
        if accum == third and i <= len_nums_m2:
            a.append(i)
        if accum == two_thirds and 1 < i <= len_nums_m1:
            b.append(i)

    bis = 0
    len_b = len(b)
    result = 0
    for n in a:
        bis = bisect(b, n, bis)
        subsize_b = len_b - bis
        result += subsize_b

    return result


def __starting_point():
    _ = int(input())
    nums = list(map(int, input().split()))
    answer = solve(nums)
    print(answer)

__starting_point()

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
k = 0
if n > 3 and s % 3 == 0:
  s //= 3
  c = [0] * n
  t = 0
  for i in range(n):
    t += a[n - i - 1]
    if t == s:
      c[n - i - 1] = 1
  for i in range(n - 1):
    c[n - i - 2] += c[n - i - 1]
  t = 0
  for i in range(n - 2):
    t += a[i]
    if t == s:
      k += c[i + 2]
print(k)

def NoW(xs):
    if sum(xs) % 3 != 0:
        return 0
    else:
        part = sum(xs) // 3
        ci = ret = 0
        acum = xs[0]
        for i, x in enumerate(xs[1:]):
            if acum == 2*part:
                # print("2. x=",x)
                ret += ci
            if acum == part:
                # print("1. x=",x)
                ci += 1
            acum += x
        
        return ret
        
input()
xs = list(map(int, input().split()))
print(NoW(xs))    

ints = int(input())
listx = list(map(int, input().split(' ')))
sumx = sum(listx)
if sumx % 3 != 0:
    print(0)

else:
    num1 = 0
    num2 = 0
    ctotal = 0
    listx.reverse()
    listx.remove(listx[0])
    listx.reverse()
    for i in listx:
        ctotal += i
        if ctotal == int(sumx*2/3):
            num2 += num1
        if ctotal == int(sumx*1/3):
            num1 += 1
    print(num2)


#input
n=int(input())
alist=[int(x) for x in input().split()]

#variables
psum=0
l=0
lim=sum(alist)//3
ways=0

#main
if sum(alist)%3!=0:
	print(0)
	quit()

for i in range(n-1):
	psum+=alist[i]
	if psum==2*lim:
		ways+=l
	if psum==lim:
		l+=1
print(ways)

n = int(input())
t = [0] + list(map(int, input().split()))
for i in range(n): t[i + 1] += t[i]
p = [0] * (n + 1)
s = t[-1]
a = s // 3
b = s - a
if s == 3 * a:
    for i in range(1, n - 1):
        p[i] += p[i - 1]
        if t[i] == a: p[i] += 1
print(sum(p[i] for i in range(1, n - 1) if t[i + 1] == b))

n = int(input())
t = list(map(int, input().split()))
q, s = 0, sum(t)
if s % 3 == 0:
    a = s // 3
    b = s - a
    s = d = 0
    for i in range(n - 1):
        s += t[i]
        if s == b: q += d
        if s == a: d += 1
print(q)

n = int(input())
a = list(map(int, input().split()))
ret, s = 0, sum(a)

if s % 3 == 0:
    p1 = s // 3
    p2 = s - p1
    s = c = 0
    for i in range(n - 1):
        s += a[i]
        if s == p2:
            ret += c
        if s == p1:
            c += 1
print(ret)


n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in a[1:]:
    b.append(b[-1] + i)
d = [a[-1]]
for i in a[:-1][::-1]:
    d.append(d[-1] + i)
d = d[::-1]
c = [0] * n
s = b[n - 1]
if b[0] * 3 == s:
    c[0] = 1
for i in range(1, n):
    if b[i] * 3 == s:
        c[i] = c[i - 1] + 1
    else:
        c[i] = c[i - 1]
ans = 0
for i in range(2, n):
    if d[i] * 3 == s:
        ans = ans + c[i - 2]
print(ans)

3

input()
nums = list(map(int, input().split()))
sum_n = sum(nums)
ans = current_sum = one_third = 0
for x in nums[:-1]:
    current_sum += x
    if current_sum == 2 / 3 * sum_n:
        ans += one_third
    if current_sum == 1 / 3 * sum_n:
        one_third += 1
print(ans)

n = int(input())
a = list(map(int, input().split()))
b = [a[0]]
for i in a[1:]:
    b.append(b[-1] + i)
d = [a[-1]]
for i in a[:-1][::-1]:
    d.append(d[-1] + i)
d = d[::-1]
c = [0] * n
s = b[n - 1]
if b[0] * 3 == s:
    c[0] = 1
for i in range(1, n):
    if b[i] * 3 == s:
        c[i] = c[i - 1] + 1
    else:
        c[i] = c[i - 1]
ans = 0

for i in range(2, n):
    if d[i] * 3 == s:
        ans = ans + c[i - 2]
print(ans)

n=int(input())
lis=input().split()
for i in range(n):
    lis[i]=int(lis[i])
lis=[0]+lis
lis1=[0]
for i in range(1,n+1):
    lis1.append(lis1[i-1]+lis[i])

if lis1[n]==0:
    lis2=[]
    for i in range(1,n):
        if lis1[i]==0:
            lis2.append(i)
    m=len(lis2)
    if m>=2:
        print(int(m*(m-1)/2))
    else:
        print(0)
else:
    lis2=[]
    lis3=[]
    for i in range(n):
        if lis1[i]==lis1[n]/3:
            lis2.append(i)
        if lis1[i]==lis1[n]*2/3:
            lis3.append(i)
    m1=len(lis2)
    m2=len(lis3)
    if m1>=1 and m2>=1:
        lis4=[0 for k in range(m1)]
        for i in range(m1):
            j=0
            while j<=m2-1 and lis3[j]<=lis2[i]:
                j+=1
            lis4[i]=m2-j
        print(sum(lis4))     
    else:
        print(0)
        


n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
if s % 3:
	print(0)
	return
cur = 0
cnt = 0
s //= 3
ans = 0
for x in a:
	cur += x
	if s == 0:
		if cur == 0:
			cnt += 1
		continue
	if cur == s:
		cnt += 1
	if cur == s * 2:
		ans += cnt
if s == 0:
	print((cnt - 1) * (cnt - 2) // 2)
else:
	print(ans)


inp=input().split(" ")
n=inp[0]
ss=0
a=[]
g=[]
inp1=input().split(" ")
p=[]
z=0

for i in range(int(n)):
    a.append(int(inp1[i]))
ans=0
s=0
for i in range(len(a)):
    s+=a[i]
if s%3!=0:
    print('0')
else:
    s//=3
    ss=0
    k=0
    l=0
    for n in a:
        k+=n
        if s==0:
            if k==0:
                l+=1
                continue
        if k==s:
            l+=1
        if k==s*2:
            ans+=l
    if s==0:
        print(((l-1)*(l-2))//2)
    else:
        print(ans)

def main():
    input()
    l = list(map(int, input().split()))
    s, res = sum(l), 0
    if not s % 3:
        s //= 3
        s2 = s * 2
        tot = t = 0
        del l[-1]
        for x in l:
            tot += x
            if tot == s2:
                res += t
            if tot == s:
                t += 1
    print(res)


def __starting_point():
    main()
__starting_point()

def solve2(n, c):
    dp = [0 for _ in range(n)]
    r = 0
    p = 0

    for i in range(n):
        dp[i] = c[i] + dp[i-1] if i > 0 else c[i]

    t = dp[n-1] // 3

    if t * 3 != dp[n-1]:
        return 0

    for i in range(n-1):
        if dp[i] == 2 * t:
            r += p
        if dp[i] == t:
            p += 1

    return r

def __starting_point():
    num_el = int(input())
    values = list(map(int, input().split()))
    print(solve2(num_el, values))
__starting_point()

n = int(input())
mas = list(map(int, input().split(" ")))
mas2 = [0] * n
mas3 = [0] * n
summ = sum(mas)
if summ % 3 != 0:
    print(0)
else:
    summ /= 3
    su=0
    schet=0
    for i in range(n):
        su+=mas[i]
        if su==summ:
            mas2[i]=1

    su=0
    schet=0
    for i in range(n):
        su+=mas[n-i-1]
        if su==summ:schet+=1
        mas3[n-i-1]=schet
    res=0
    for i in range(n-2):
        if mas2[i]:res+=mas3[i+2]
    print(res)

import bisect

n = int(input())
a = [int(x) for x in input().split()]
s, p, k = sum(a), a[0], sum(a) / 3
b, c = [], []
for i in range(len(a)):
    if s == k:
        c.append(i)
    if p == k:
        b.append(i)
    s -= a[i]
    if i < n - 1:
        p += a[i+1]
if (len(b) != 0) and (b[-1] == n-1):
    b = b[:-1]
if (len(c) != 0) and (c[0] == 0):
    c = c[1:]
res = 0
e = len(c)
for i in b:
    res += e - bisect.bisect_left(c, i + 2)
print(res)