C. Количество способов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задан массив a[1], a[2], ..., a[n], состоящий из n целых чисел. Посчитайте количество способов разбить все элементы массива на три непрерывные части так, чтобы сумма элементов в каждой части была одинаковой.

Более формально, нужно найти количество таких пар индексов i, j (2 ≤ i ≤ j ≤ n - 1), что .

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 5·105) — количество чисел в массиве. Во второй строке записаны n целых чисел a[1], a[2], ..., a[n] (|a[i]| ≤  109) — элементы массива a.

Выходные данные

Выведите единственное целое число — количество способов разбить массив на три части с одинаковой суммой.

Примеры
Входные данные
5
1 2 3 0 3
Выходные данные
2
Входные данные
4
0 1 -1 0
Выходные данные
1
Входные данные
2
4 1
Выходные данные
0