Cho một dãy mô tả nhiệt độ của các ngày gồm các số nguyên từ \(1\) đến \(N\), mỗi số xuất hiện đúng một lần. Ở mỗi bước, tìm ngày có nhiệt độ cao nhất và thấp nhất trong dãy, sau đó tách dữ liệu của các ngày nằm trong đoạn giữa hai ngày này (kể cả 2 ngày đó) thành một nhóm. Dữ liệu của các ngày còn lại được nối thành dãy mới (giữ nguyên thứ tự). Lặp lại quy trình trên dãy mới cho đến khi dãy rỗng và đếm số nhóm đã tách được.

Input

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(1 \le N \le 2 \cdot 10^5\)).
• Dòng tiếp theo gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le N\)).

Output

• Ghi ra một số nguyên duy nhất là số nhóm tách được.

Scoring

• Subtask \(1\) (\(2.0\) điểm): \(N \le 2000\).
• Subtask \(2\) (\(2.5\) điểm): Sau mỗi thao tác tách nhóm, ngày đầu tiên trong dãy mới luôn là ngày có nhiệt độ thấp nhất.
• Subtask \(3\) (\(2.5\) điểm): Không có ràng buộc nào thêm.

Example

6
3 5 1 4 6 2

3

7
1 6 2 7 3 4 5

2