Một nhóm có \(n\) người bạn, các bạn được đánh số hiệu từ \(1\) đến \(n\) đứng thành một hàng ngang để cùng nhau chụp ảnh. Vị trí thứ \(i\) là người \(p_i\) \((1 \leq p_i \leq n)\) đứng. Sau bức ảnh chụp chung cả \(n\) người, một số bạn muốn chụp chung cùng nhau. Cụ thể, các bạn đứng từ vị trí \(L\) đến vị trí \(R\) \((1 \leq L \leq R \leq n)\) giữ nguyên vị trí, các bạn từ \(1\) đến \((R-1)\) và các bạn đứng từ \((R+1)\) đến \(n\) rời khỏi hàng. Một cách chọn \((L,R)\) được gọi là đẹp nếu tập số hiệu của các bạn đứng từ vị trí \(L\) đến vị trí \(R\) là một tập gồm các số hiệu liên tiếp nhau.

Yêu cầu: Cho dãy số nguyên dương \(p_1, p_2, ..., p_n\), hãy đếm số cách chọn \((L,R)\) đẹp.

Input

• Dòng đầu chứa số nguyên dương \(n\) \((n \leq 3 \cdot 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên dương \(p_1, p_2, ..., p_n\) (là một hoán vị của \(1, 2, ..., n\))

Output

• In ra một dòng chứa một số là số cách chọn \((L,R)\) đẹp.

Scoring

• Subtask \(1\) (\(30\%\)): \(n \leq 100\)
• Subtask \(2\) (\(20\%\)): \(n \leq 5000\)
• Subtask \(3\) (\(25\%\)): \(n \leq 50000\)
• Subtask \(4\) (\(25\%\)): Không có ràng buộc gì thêm

Example

5
1 5 3 4 2

10