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 DD.INP

• Dòng đầu tiên là số nguyên dương N, thỏa mãn: ~1 \le N \le 10^5~
• Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N, thỏa mãn: ~1 \le A_i \le N~, ~1 \le i \le N~

Kết quả DD.OUT

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

Ràng buộc

• Có 30% số test tương ứng 30% số điểm với N ≤ 200.
• 30% số test tương ứng 30% số điểm với N ≤ 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 với N ≤ 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.

Ví dụ

DD.INP

3
1 2 3

DD.OUT

6

Giải thích: Có 6 dãy con đẹp là: {1}, {2}, {3}, {1,2}, {2,3}, {1,2,3}.