Talulu rất thích những dãy số không có phần tử nào lặp lại. Một ngày nọ, Talulu được giao cho một mảng số nguyên có độ dài ~N~. Talulu muốn biết có bao nhiêu dãy con liên tiếp trong mảng mà mỗi giá trị chỉ xuất hiện một lần duy nhất.

Một dãy con liên tiếp là một đoạn gồm các phần tử liền kề trong mảng ban đầu. Ví dụ, với dãy [4, 5, 6], thì [5, 6] là một dãy con liên tiếp hợp lệ, còn [4, 6] thì không.

Ví dụ, dãy 5, 1, 2, 1 có một vài dãy con liên tiếp như:

• [5], [1], [2], [1], [5, 1], [1, 2], [2, 1], [5, 1, 2] là hợp lệ vì không có phần tử nào bị lặp.
• [1, 2, 1] thì không hợp lệ vì số 1 xuất hiện 2 lần.

Talulu nhờ TeoCheow giúp mình đếm xem có bao nhiêu dãy con liên tiếp như vậy. Bạn có thể giúp TeoCheow không?

Input

• Dòng đầu tiên là số nguyên ~N~ ~(1 ≤ N ≤ 10^6)~ — số lượng phần tử trong mảng.
• Dòng thứ hai là ~N~ số nguyên ~A_1, A_2, ..., A_n~ ~( A_i ≤ 10^9)~ — các phần tử trong mảng.

Output

• In ra một số nguyên là số lượng dãy con liên tiếp không chứa phần tử lặp.

📌 Example

Input

4
1 2 1 2

Output

7

💡 Explanation

Các dãy con hợp lệ là:

• [1], [2], [1], [2]
• [1, 2], [2, 1], [1, 2]

Dãy [1, 2, 1] hoặc [2, 1, 2] hoặc [1, 2, 1, 2] không hợp lệ vì có số lặp.