Играта Плочка (или некаде позната како Царица) се игра со исцртување на квадратни полиња, најчесто едно по друго, запишување на број во секое поле и скокање по полињата по редослед.

Во оваа задача имаме една дооолга низа од N исцртани полиња, едно по друго (1-во, 2-ро, … до N-то) и во секое од нив запишано по еден цел број. За дадени L и R (1 ≤ L ≤ R ≤ N), таткото на Ана и Ема ги носи нив до L-тото поле и им дава задача да скокаат до R-тото поле, прескокнувајќи по едно поле. При тоа, Ана скока почнувајќи од L-тото поле, а Ема почнувајќи од (L+1)-вото поле. Дури скокаат, тие ги собираат сите броеви на полињата на кои застанале.

Фактички кај Ана ќе се соберат сите броеви од интервалот меѓу L-тото и R-тото поле кои се на непарни позиции, а кај Ема тие на парни позиции.

Ако по завршувањето на скокањето и собирањето на броевите Ана и Ема имаат добиено различен збир, избива кавга. Затоа татко им се труди да најде такви L и R за кои тие ќе добијат еднакви збирови, после играњето.

Ваша задача е да утврдите за дадената низа од полиња колку ралични парови (L, R) постојат, такви што ќе дадат еднакви збирови за Ана и Ема. Два пара се различни меѓу себе ако се разликуваат во барем еден од двата броја.

Влез

Во првиот ред е даден еден цел број N (1 ≤ N ≤ 10⁵) – големина на низата. Во вториот ред се дадени N цели броеви a_i (−10⁹ ≤ a_i ≤ 10⁹) - елементите на низата.

Забелешка.
Подзадача 1: 10 поени, N ≤ 100, −10 ≤ a_i ≤ 10
Подзадача 2: 20 поени, N ≤ 1500, −10 ≤ a_i ≤ 10
Подзадача 3: 30 поени, N ≤ 10⁵, −10 ≤ a_i ≤ 10
Подзадача 4: 40 поени, N ≤ 10⁵, −10⁹ ≤ a_i ≤ 10⁹

Во финалните резултати, поените за дадена подзадача ќе се доделат само ако се успешни сите тест случаи за таа подзадача како и тест случаите од сите претходни подзадачи.

Излез

Во првиот ред на стандардниот излез отпечатете еден цел број – бараниот број на парови.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 128 megabytes

Примери

влез
7
1 2 1 3 4 1 1

излез
6

влез
2
0 0

излез
3

Објаснување на првиот пример: Парови кои даваат еднакви збирови се: (6, 7), т.е. елементите [1 1], (1, 3) т.е. [1 2 1], (4, 6) т.е. [3 4 1], (2, 5) т.е. [2 1 3 4], (1, 6) т.е. [1 2 1 3 4 1], (2, 7) т.е. [2 1 3 4 1 1]. На пример во [1 2 1] Ана ќе собере 1+1=2, а Ема ќе има само еден собирок т.е. 2, додека во [1 2 1 3 4 1] Ана ќе собере 1+1+4 = 6, а Ема 2+3+1 = 6, што значи еднакви збирови за двете.
Објаснување на вториот пример: Парови кои даваат еднакви збирови се: (1, 1), (2,2) и (1, 2). Во сите три случаи и збировите на Ана и Ема се по 0.