Một dãy số được gọi là đẹ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 đẹp.

• ~[3, 3, 3, 4, 4]~, ~[7, 7, 8, 7]~ và ~[100, 100, 100]~ không phải là các dãy đẹp.

Cho dãy ~A~ độ dài ~N~, hãy đếm số cặp chỉ số ~(l, r)~ với ~1 \le l \le r \le N~ sao cho dãy con ~A_l, A_{l+1}, . . . , A_r~ là dãy đẹp.

Dữ liệu

• Dòng đầu tiên: gồm số nguyên ~N (1 \le N \le 500 000)~ — độ dài dãy ~A~. • Dòng thứ hai: gồm ~N~ số nguyên ~A_1, A_2, . . . A_n~ ~(1 \le A_i \le 500 000)~ — các phần tử của dãy ~A~.

Kết quả

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

Sample Input 1

4
1 2 1 1

Sample Output 1

9

Sample Input 2

6
4 5 4 5 4 5

Sample Output 2

18

Giải thích ví dụ

• Ở ví dụ thứ nhất, 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]~)

Scoring

• Subtask ~1~ (~20~% số điểm): ~N \le 50~, ~A_i \le 50~

• Subtask ~2~ (~15~% số điểm): ~N \le 500~, ~A_i \le 500~

• Subtask ~3~ (~15~% số điểm): ~N \le 5000~, ~A_i \le 5000~

• Subtask ~4~ (~50~% số điểm): Không có ràng buộc gì thêm