Trong giờ số học, cô giáo đưa ra dãy số \(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 \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)\).

Output

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

Example

3
1 2 3

6

3
2 2 1

4

Ràng buộc

• Có \(30\%\) số test tương ứng \(30\%\) số điểm có \(N \leq 200\).
• \(30\%\) số test tương ứng \(30\%\) số điểm có \(N \leq 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 \leq 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.