Cho trước số nguyên dương ~n~ và dãy số nguyên ~a_1,a_2,\dots,a_n~. Một dãy con liên tiếp ~a_l,a_{l+1},\dots,a_r~ ~(1 \le l \le r \le n)~ được gọi là dãy số đẹp nếu mỗi phần tử trong dãy đều có số lần xuất hiện không vượt quá ~2~.

Ví dụ: ~\{1;5;2;4;3\}~, ~\{6;10;10;6\}~ và ~\{9\}~ là các dãy số đẹp; ~\{3;3;4;4;4\}~, ~\{7;7;8;7\}~ và ~\{100;100;100\}~ không phải là dãy số đẹp vì mỗi dãy đều có ít nhất một phần tử có số lần xuất hiện lớn hơn ~2~.

Yêu cầu: Hãy đếm số lượng cặp chỉ số ~(l,r)~ ~(1 \le l \le r \le n)~ sao cho dãy con ~a_l,a_{l+1},\dots,a_r~ là dãy số đẹp.

Input

• Dòng thứ nhất chứa số nguyên ~n~ ~(1 \le n \le 5 \cdot 10^5)~, số lượng phần tử của dãy;

• Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,\dots,a_n~ ~(1 \le a_i \le 5 \cdot 10^5, 1 \le i \le n)~ lần lượt là các giá trị của dãy, mỗi số cách nhau một khoảng trắng.

Output

Một số nguyên duy nhất là số lượng cặp chỉ số ~(l,r)~ thỏa mãn yêu cầu đề bài.

Scoring

Sample Input 1

4
1 2 1 1

Sample Output 1

9

Notes

Có ~9~ cặp chỉ số ~(l,r)~ thỏa mãn yêu cầu đề bài:

• ~l=1,r=1~ (dãy ~\{1\}~);

• ~l=1,r=2~ (dãy ~\{1;2\}~);

• ~l=1,r=3~ (dãy ~\{1;2;1\}~);

• ~l=2,r=2~ (dãy ~\{2\}~);

• ~l=2,r=3~ (dãy ~\{2;1\}~);

• ~l=2,r=4~ (dãy ~\{2;1;1\}~);

• ~l=3,r=3~ (dãy ~\{1\}~);

• ~l=3,r=4~ (dãy ~\{1;1\}~);

• ~l=4,r=4~ (dãy ~\{1\}~).