Cho mảng \(A\) gồm \(n\) phần tử nguyên. Đếm số lượng dãy con liên tiếp mà không có giá trị nào xuất hiện quá \(2\) lần.

Ví dụ \(3, 2, 3\) không thỏa mãn vì giá trị \(3\) xuất hiện \(2\) lần.

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(A_i\).

Output

• In ra số lượng dãy con thỏa mãn.

Điều kiện

• \(1 \le n \le 10^{5}\)
• \(1 \le A_i\le 10^{9}\);

Sample Input 1

4
1 2 1 2

Sample Output 1

7