Трішки формальних умов нікому не завадять

Вам надано масив попарно різних цілих чисел $a_1,a_2,\dots ,a_n$.

Підрахуйте кількість пар $(l,r)$ $(1\le l\le r\le n)$, де $a_l+\cdots +a_k=a_k+\cdots +a_r$ і $k$ — це позиція максимального елемента серед $a_l,a_{l+1},\dots ,a_{r-1},a_r$.

Вхідні дані

Перший рядок містить одне ціле число $n$ ($1\le n\le 3\cdot 10^5$) — довжина масиву $a$.

Другий рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($-10^9\le a_i\le 10^9$) — елементи масиву $a$.

Гарантується, що всі цілі числа в масиві є попарно різними.

Вихідні дані

Виведіть одне ціле число — кількість пар $(l,r)$, описаних в умові.

Приклади

Примітка

У першому прикладі масив — $a=[1,3,5,4,2]$. Є $6$ пар $(l,r)$, які задовольняють умову:

1. $l=1$, $r=4$; в цьому випадку $k$ дорівнює $3$, оскільки $5$ є максимальним серед $[1,3,5,4]$; пара $l=1$, $r=4$ відповідає умові, оскільки $1+3+5=5+4$;

2. $l=1$, $r=1$;

3. $l=2$, $r=2$;

4. $l=3$, $r=3$;

5. $l=4$, $r=4$;

6. $l=5$, $r=5$.

Оцінювання

1. ($3$ бали): $n\le 100$;

2. ($7$ балів): $n\le 10^3$;

3. ($13$ балів): $a_1<a_2<\cdots <a_n$;

4. ($8$ балів): існує $i$ $(1\le i\le n)$, таке, що $a_1<\cdots <a_i$ та $a_i>\cdots >a_n$;

5. ($22$ бали): $n\le 10^5$;

6. ($23$ бали): масив складається з випадкових цілих чисел $(-10^9\le a_i\le 10^9)$;

7. ($24$ бали): немає додаткових обмежень.