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 sắp xếp ~B~ theo thứ tự tăng dần thu đượ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, 1\}~ là dãy đẹp, trong khi ~B = \{2, 3, 2\}~ thì không.

Yêu cầu: Hãy giúp cá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ữ liệu được đọc từ file văn bản DD.INP.
• Dòng đầu tiên bao gồm số nguyên dương ~N~ (~1 \leq N \leq 10^{5}~).
• Dòng thứ hai bao gồm ~N~ số nguyên ~A_{1}, A_{2}, ..., A_{N}~ (~1 \leq A_{i} \leq N, 1 \leq i \leq N~).

Output

• Ghi kết quả ra file văn bản DD.OUT.

Scoring

• Subtask ~1~ ~(30\%)~: ~N \leq 200~.
• Subtask ~2~ ~(30\%)~: ~N \leq 2000~ và các phần tử của ~A~ đôi một phân biệt.
• Subtask ~3~ ~(20\%)~: ~N \leq 10^{5}~ và các phần tử của ~A~ đôi một phân biệt.
• Subtask ~4~ ~(20\%)~: Không có ràng buộc về ~A~.

Example input 1

3 
1 2 3

Example output 1

6

Note 1

• Có ~6~ dãy con đẹp: ~\{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,2,3\}~.

Example input 2

2 
2 1

Example output 2

4

Note 2

• Có ~4~ dãy con đẹp: ~\{2\}, \{2,1\}, \{1\}, \{2,1\}~.