Сиқырлы патшалықта сиқырлы шарлармен байланысты ежелгі тепе-теңдік ритуалы бар. Әр шардың өз сиқырлы энергиясы бар, ол массивте \(a_1,\ldots,a_n\) сандарымен көрсетілген.

Жоғарғы сиқыршы шынжырды үш топқа бөлуге тырысады, сонда бірінші топтың жалпы сиқырлы энергиясынан екінші топтың энергиясын алып тастағанда, үшінші топтың энергиясына тең болады. Сонымен қатар, әр топ бос болмауы керек және бір топтағы сандар бір-бірінің артынан келуі тиіс. Ежелгі тепе-теңдік ритуалын орындауға көмектесіңіз!

Ресми түрде, ол шынжырды үш бөлікке \((i, j)\) индекстерімен кесу тәсілдерін іздейді, мұнда \(1 < i \leq j < n\), сонда мына теңдік орындалады: \[S_{\text{сол}} - S_{\text{орта}} = S_{\text{оң}}\]

мұнда:

• \(S_{\text{сол}} = \sum\limits_{k=1}^{i-1} a_k\) — \(i-1\)-ге дейінгі сол жақтағы шарлардың жалпы энергиясы,

• \(S_{\text{орта}} = \sum\limits_{k=i}^{j} a_k\) — \(i\)-ден \(j\)-ға дейінгі шарлардың жалпы энергиясы,

• \(S_{\text{оң}} = \sum\limits_{k=j+1}^{n} a_k\) — \(j+1\)-ден соңына дейінгі шарлардың жалпы энергиясы.

Сіздің міндетіңіз — сиқыршыға осы теңдікке сәйкес келетін \((i, j)\) бөлулерінің мүмкін болатын жұптарының санын табуға көмектесу.

Енгізу

Бірінші жолда бір сан \(n\) (\(3 \leq n \leq 10^5\)) — шарлардың саны.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) (\(|a_k| \leq 10^9\)) — шарлардың сиқырлы энергиясының мәндері.

Шығару

Бір санды шығарыңыз — теңдікке сәйкес келетін \((i, j)\) индекстерін таңдау тәсілдерінің саны.

Мысалдар

Енгізу 1

3
100 7 93

Жауап 1

1

Енгізу 2

6
3 -4 -8 -2 9 8

Жауап 2

4

Ескертпелер

Бірінші мысалда жалғыз сәйкес бөліну \((i,j) = (2,2)\).

Екінші мысалда 4 мүмкін бөліну бар:

• \(i = 2, j = 2\): \((3) - (-4) = (-8) + (-2) + 9 + 8 \to 3 - (-4) = 7\),

• \(i = 2, j = 3\): \((3) - (-4 + (-8)) = (-2) + 9 + 8 \to 3 - (-12) = 15\),

• \(i = 2, j = 4\): \((3) - (-4 + (-8) + (-2)) = 9 + 8 \to 3 - (-14) = 17\),

• \(i = 2, j = 5\): \((3) - (-4 + (-8) + (-2) + 9) = 8 \to 3 - (-5) = 8\).