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 con đẹp của ~A~ theo yêu cầu của cô giáo.

Input

• 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~).

Output

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

Sample Input 1

3 
1 2 3

Sample Output 1

6

Giải thích: Có 6 dãy con đẹp là: ~\{1\}, \{2\}, \{3\}, \{1, 2\}, \{2, 3\}, \{1, 2, 3\}~.

Sample Input 2

3 
2 2 1

Sample Output 2

4

Giải thích: Có 4 dãy con đẹp là: ~\{2\}, \{2\}, \{1\}, \{2, 1\}~.

Subtasks

• Có 30% số test tương ứng 30% số điểm có ~N \le 200~.
• 30% số test tương ứng 30% số điểm có ~N \le 2000~ và các phần tử của ~A~ đôi một phân biệt.
• 20% số test tương ứng 20% số điểm có ~N \le 10^5~ và các phần tử của ~A~ đôi một phân biệt.
• 20% số test còn lại tương ứng 20% số điểm không có ràng buộc gì thêm.