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í du, \(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:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (1 \leq n \leq 10^{5})\)

+ Dòng thứ hai chứa \(n\) số nguyên dương \(a_{1},\ a_{2},\ \ldots,\ a_{n}\ (1 \leq a_{i} \leq n,\ 1 \leq i \leq n)\)

Kết quả:

+ Ghi một số nguyên dương duy nhất là số lượng dãy con đẹp của \(A\).

Ví dụ:

Ràng buộc:

+ 30% test có \(n \leq \ 200\)

+ 30% test có \(n\ \leq \ 2000\) và các phần tử của \(A\) đôi một phân biệt

+ 20% test có \(n \leq 10^{5}\) và các phần tử của \(A\) đôi một phân biệt.

+ 20% test không có ràng buộc gì thêm.