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, 9, 9, 6], [100]~ 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~ có ~n~ phần tử, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~a_l, a_{l+1}, ..., a_r~ là dãy đẹp.

Input

• Dòng đầu tiên chứa số nguyên dương ~n;~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(l, r)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 50; \ a_i \le 50;~
• Subtask 2 [15%]: ~n \le 500; \ a_i \le 500;~
• Subtask 3 [15%]: ~n \le 5000; \ a_i \le 5000;~
• Subtask 4 [50%]: ~n \le 5 \times 10^5; \ a_i \le 5 \times 10^5.~

Examples

Input

4
1 2 1 1

Output

9

Giải thích: Các cặp chỉ số ~(l, r)~ thoả mãn đề bài là: ~(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).~

Input

6
4 5 4 5 4 5

Output

18