Cho dãy số nguyên ~A~ độ dài ~N~. Đếm xem có bao nhiêu dãy con liên tiếp từ ~l~ đến ~r~ thỏa mãn điều kiện sau:

• Gọi ~k~ là số nhỏ nhất trong dãy từ ~l~ đến ~r~ thì các số ~k, k + 1, k + 2,...,k + r − l~ xuất hiện đúng một lầ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_i~.

Output

• In ra một số nguyên duy nhất là kết quả cần tìm.

Sample

Input #1

5
1 3 2 4 5

Output #1

12

Input #2

3
1 1 1

Output #2

3

Hint

• Trong test ví dụ đầu tiên, các bộ ~(l, r)~ thỏa mãn là: ~(1, 1), (1, 3), (1, 4), (1, 5), (2, 2), (2, 3), (2, 4), (2, 5), (3, 3), (4, 4), (4, 5), (5, 5)~.

Problem source: Kc97ble - Free Contest