Виртуальное соревнование – это способ прорешать прошедшее соревнование в режиме, максимально близком к участию во время его проведения. Поддерживается только ICPC режим для виртуальных соревнований.
Если вы раньше видели эти задачи,
виртуальное соревнование не для вас – решайте эти задачи в архиве.
Если вы хотите просто дорешать задачи, виртуальное соревнование не для вас – решайте эти задачи в архиве.
Запрещается использовать чужой код, читать разборы задач и общаться по содержанию соревнования с кем-либо.
Задан массив 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.
Выходные данные
Выведите единственное целое число — количество способов разбить массив на три части с одинаковой суммой.