Cấp số cộng

Time limit: 1.0s , Memory limit: 256M , Points: 1

Cho dãy số nguyên $a$ ~a~ gồm $n$ ~n~ phần tử được đánh số từ $1$ ~1~ đến $n$ ~n~. Bạn hãy đếm số lượng cặp chỉ số $(l,r)$ ~(l,r)~ $(1 \le l \le r \le n)$ ~(1 \le l \le r \le n)~ thỏa mãn dãy con liên tiếp $a_l,a_{l+1},...,a_r$ ~a_l,a_{l+1},...,a_r~ tạo thành một cấp số cộng.

Dãy $x_1,x_2,...,x_k$ ~x_1,x_2,...,x_k~ là một dãy cấp số cộng khi và chỉ khi tồn tại một số nguyên $d$ ~d~ thỏa mãn $x_{i+1}-x_i=d$ ~x_{i+1}-x_i=d~ với mọi $1 \le i < k$ ~1 \le i < k~.

Input

Dòng đầu tiên chứa số nguyên $n$ ~n~ $(1 \le n \le 2 \times 10^5)$ ~(1 \le n \le 2 \times 10^5)~.
Dòng thứ hai chứa $n$ ~n~ số nguyên của dãy $a$ ~a~ $(1 \le a_i \le 10^9)$ ~(1 \le a_i \le 10^9)~.

Output

In ra số lượng cặp chỉ số $(l,r)$ ~(l,r)~ thỏa mãn.

Examples

Sample Input 1

4
1 2 3 5

Sample Output 1

Sample Input 2

3
3 5 7

Sample Output 2

Notes

Trong ví dụ đầu tiên, các cặp chỉ số $(l,r)$ ~(l,r)~ thỏa mãn bao gồm: $(1,1)$ ~(1,1)~ $,$ ~,~ $(2,2)$ ~(2,2)~ $,$ ~,~ $(3,3)$ ~(3,3)~ $,$ ~,~ $(4,4)$ ~(4,4)~ $,$ ~,~ $(1,2)$ ~(1,2)~ $,$ ~,~ $(2,3)$ ~(2,3)~ $,$ ~,~ $(3,4)$ ~(3,4)~ $,$ ~,~ $(1,3)$ ~(1,3)~.