Dãy đẹp

Trong giờ số học, cô giáo đưa ra dãy $A$ gồm $N$ số nguyên dương, mỗi số có giá trị 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 (sắp xếp được $2,3,4$) trong khi $B=\{2,3,2\}$ thì không (sắp xếp được $2,2,3$, có hai số bằng nhau).

Hai dãy con ở các vị trí khác nhau được tính là khác nhau, kể cả khi chúng gồm cùng các giá trị.

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

Dữ liệu ra

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

Ràng buộc

• $1\le N\le {10}^5$.
• $1\le A_i\le N$.

Subtasks

• $30\%$ số test ứng với $30\%$ số điểm có $N\le 200$.
• $30\%$ số test ứng với $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 ứng với $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 ứng với $20\%$ số điểm không có ràng buộc gì thêm.

Điểm được tính theo từng test.

Ví dụ