Cần sắp xếp dãy số nguyên \(a_1, a_2, \ldots, a_n\) theo thứ tự không giảm. Có \(n\) máy sẵn sàng thực hiện việc sắp xếp, do đó người ta muốn cắt dãy \(a_1, a_2, \ldots, a_n\) thành nhiều đoạn nhất, lần lượt mỗi đoạn theo thứ tự từ đầu tới cuối được chuyển cho từng máy tính để thực hiện việc sắp xếp. Sau khi các máy sắp xếp xong, ghép lần lượt các đoạn lại để nhận được dãy theo thứ tự không giảm.

Yêu cầu: Cho dãy số nguyên \(a_1, a_2, \ldots, a_n\), hãy tính số lượng đoạn nhiều nhất có thể cắt.

Input

• Dòng đầu chứa số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Gồm một dòng chứa một số là số lượng đoạn nhiều nhất có thể cắt.

Example

5
3 2 1 4 5

3

Scoring

• Subtask \(1\): \(n \le 20\).
• Subtask \(2\): \(n \le 2000\).
• Subtask \(3\): \(n \le 200000\).