Задан массив 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
| Codeforces Round 266 (Div. 2) |
|---|
| Закончено |
