Đua nhau on top

Cho mảng \(a\) gồm \(n\) số nguyên. Một đoạn con liên tiếp \([l, r]\) được gọi là "đầy đủ" nếu nó chứa tất cả các giá trị khác nhau xuất hiện trong mảng \(a\).

Hãy đếm số lượng đoạn con liên tiếp \([l, r]\) (\(1 \le l \le r \le n\)) thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau bởi dấu cách.

Output

• Một số nguyên duy nhất là số lượng đoạn con liên tiếp đầy đủ tìm được.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(|a_i| \le 10^9\)

Example

5
1 2 1 3 2

5