Dãy đẹp

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.

Dữ liệu vào từ tệp văn bản DD.INP:

• 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, \ldots, A_N$ ($1 \le A_i \le N, 1 \le i \le N$).

Kết quả ghi ra tệp văn bản DD.OUT: Một số nguyên duy nhất là số lượng dãy con đẹp của $A$.

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