Организатор выстроил участников в колонну. Для каждого участника известно целое число — его вклад в общую сумму своей будущей группы.

Нужно посчитать, сколькими способами можно разделить колонну на три непустые подряд идущие группы так, чтобы сумма чисел в каждой из трёх групп была одинаковой.

Иначе говоря, требуется выбрать две точки разбиения, которые делят исходную последовательность на три последовательных непустых отрезка с равными суммами.

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

Первая строка содержит одно целое число n — количество участников в колонне.

Вторая строка содержит n целых чисел a_i — значения, записанные у участников.

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

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

Ответ может не помещаться в 32-битный целочисленный тип.

Ограничения

• 3 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9

Примеры

Пример 1

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

4
1 3 4 4

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

1

Пояснение

Сумма 12, треть 4; части [1,3], [4], [4] дают суммы по 4 — единственное разбиение.

Пример 2

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

3
1 1 1

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

1