Armenian Olympiads

Ենթազանգվածներ

Ամբողջ թվերի զանգվածը կանվանենք «արդար», եթե կենտ ինդեսքներով տարրերի գումարը հավասար է զույգ ինդեքսներով տարրերի գումարին։

Տրված է n երկարության ամբողջ թվերի հաջորդականություն։ Պահանջվում է գրել ծրագիրը, որը ներածում է հաջորդականությունը, պահում է այն զանգվածի մեջ, ապա հաշվում է, բոլոր «արդար» ենթազանգվածների քանակը։ Ենթազանգված ասելով, հասկանում ենք զանգվածի ինչ-որ L ինդեքսով տարրից մինչև R ինդեսքով տարրը (L < R) բոլոր իրար հաջորդտող տարրերը։

Մուտքային տվյալներ

Առաջին տողում տրված է հաջորդականության n երկարությունը (1≤n≤105)(1 ≤ n ≤ 10^5): Երկրորդ տողում տողում տրված են n ամբողջ թվեր` հաջորդականության aᵢ՝ տարրերը (−109≤ai≤109)(-10^9≤a_i≤10^9)։

Ելքային տվյալներ

Պետք է արտածել մեկ թիվ՝ պահանջվող քանակը։

Օրինակ

Մուտք

Ելք

7
1 2 1 3 4 1 1

6

2
0 0

3

Առաջին օրինակում «արդար» են [1 2 1], [1 3 4], [1 1], [2 1 3 4], [2 1 3 4 1 1], [3 4 1] ենթազանգվածները

Ենթախնդիրներ

Համար

Սահմանափակում

Միավոր

0

Օրինակ

0

1

n≤100,−10≤𝑎𝑖≤10n ≤ 100, −10≤𝑎_𝑖≤10

10

2

n≤1500,−10≤𝑎𝑖≤10n ≤ 1500, −10≤𝑎_𝑖≤10

20

3

n≤105,−10≤𝑎𝑖≤10n ≤ 10^5, −10≤𝑎𝑖≤10

30

5

Լրացուցիչ սահմանափակումներ չկան

40

Constraints

Time limit: 1.6 seconds

Memory limit: 512 MB

Output limit: 1 MB