Cho một mảng ~a~ gồm ~n~ số. Một mảng được gọi là đẹp khi mỗi giá trị xuất hiện trong mảng đều có số lần xuất hiện bằng nhau.

Ví dụ:

• ~[1, 1]~ là mảng đẹp vì chỉ có giá trị ~1~.

• ~[1, 2, 1, 2]~ là mảng đẹp vì giá trị ~1~ và ~2~ đều xuất hiện ~2~ lần.

• ~[1, 2, 1, 2, 3]~ không phải mảng đẹp vì giá trị ~3~ xuất hiện ~1~ lần trong khi ~1~ và ~2~ xuất hiện ~2~ lần.

Nhiệm vụ của bạn là tính xem có bao nhiêu mảng con† của mảng ~a~ là mảng đẹp.

†: Mảng con là mảng không rỗng còn lại sau khi xóa đi một số (hoặc không) phần tử đứng đầu và đứng cuối trong mảng ban đầu.

Input

Dòng đầu tiên gồm ~1~ số nguyên dương ~n~ ~(n \le 2 \cdot 10^5)~ mô tả độ dài của mảng ~a~.

Dòng tiếp theo gồm ~n~ số nguyên dương mô tả các phần tử của mảng ~a~ ~(a_i \le 2 \cdot 10^5)~.

Output

In ra ~1~ số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

5
1 2 1 2 3

Sample Output 1

11