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 đẹ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, ... A_n\) \((1 \le A_i \le N, 1 \le i \le N)\)

Dữ liệu ra

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

Ràng buộc

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

Input 1

3
1 2 3

Output 1

6

Giải thích

Có 6 dãy con đẹp là {1},{2},{3},{1,2},{2,3},{1,2,3}

Input 2

3
2 2 1

Output 2

4

Giải thích

Có 4 dãy con đẹp là {2},{2},{1},{2,1}