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

• Xuất ra màn hình 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.

Example

4
1 2 1 1

9

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.