Trong giờ số học, cô giáo đưa ra dãy $A$ gồm $N$ số nguyên dương từ $1$ đến $N$. Cô cho mỗi học sinh chọn một dãy con $B$ gồm các phần tử liên tiếp của $A$. Dãy con $B$ được gọi là dãy đẹp nếu ta sắp xếp $B$ theo thứ tự tăng dần thì được một dãy số nguyên liên tiếp. Dãy con chỉ gồm một phần tử cũng được gọi là dãy đẹp. Ví dụ, B={2,4,3} là dãy đẹp trong khi B={2,3,2} thì không.

Yêu cầu

• Hãy giúp cả lớp đếm số lượng dãy đẹp của $A$ theo yêu cầu của cô giáo.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương $N$ $(1\le N\le {10}^5)$
• Dòng thứ hai chứa $N$ số nguyên dương $A_1,A_2,...A_n$ $(1\le A_i\le N,1\le i\le N)$

Dữ liệu ra

• Một số nguyên duy nhất là số lượng dãy con đẹp của $A$.

Ràng buộc

• 30% test có $N\le 200$
• 30% test có $N\le 2000$ và các phần tử của $A$ đôi một phân biệt.
• 20% test có $N\le {10}^5$ và các phần tử của $A$ đôi một phân biệt
• 20% test còn lại ràng buộc gì thêm

Input 1

3
1 2 3

Output 1

6

Giải thích

Có 6 dãy con đẹp là {1},{2},{3},{1,2},{2,3},{1,2,3}

Input 2

3
2 2 1

Output 2

4

Giải thích

Có 4 dãy con đẹp là {2},{2},{1},{2,1}