Mảng ~A~ gồm ~N~ phần tử là hoán vị của các giá trị từ ~1~ đến ~N~. Bạn được phép chia mảng ~A~ thành ~K~ đoạn, trong đó mỗi đoạn gồm các phần tử liên tiếp có độ dài tùy ý có thể khác nhau.

Ví dụ một phép chia thành 5 đoạn: ~[4]~ ~[2 \ 1]~ ~[5]~ ~[9 \ 8 \ 7 \ 6 \ 3]~ ~[10]~

Sau khi chia thành ~K~ đoạn, bạn được phép thực hiện sắp xếp các giá trị bên trong mỗi đoạn (độc lập với nhau).

Yêu cầu: Hãy xác định số đoạn ~K~ lớn nhất có thể sao cho sau khi thực hiện sắp xếp xong thì mảng ~A~ trở thành mảng được sắp xếp tăng dần.

Input

• Dòng đầu ghi số nguyên ~N~ là số lượng phần tử của mảng ~(1 \le N \le 10^{4})~.

• Dòng tiếp theo ghi ~N~ số nguyên ~A_i~ là giá trị của các phần tử trong mảng ~(1 \le A_{i} \le N)~.

Output

Một giá trị duy nhất là số lượng ~K~ theo yêu cầu.

Scoring

Sample Input 1

5
4 5 3 2 1

Sample Output 1

1

Sample Input 2

5
1 2 4 5 3

Sample Output 2

3

Sample Input 3

10
4 2 1 5 9 8 7 6 3 10

Sample Output 3

2

Notes

• Ví dụ 1: Chỉ có thể chia thành đúng một đoạn gồm tất cả các phần tử của ~A~ rồi sắp xếp để được dãy theo yêu cầu ~[4 \ 5 \ 3 \ 2 \ 1] \rightarrow [1 \ 2 \ 3 \ 4 \ 5]~.

• Ví dụ 2: Có thể chia thành nhiều nhất 2 đoạn như sau: ~[1 \ 2]~ và ~[4 \ 5 \ 3] \rightarrow [1 \ 2]~ và ~[3 \ 4 \ 5]~, mảng ~A~ đã được sắp xếp.

• Ví dụ 3: Có thể chia thành nhiều nhất 2 đoạn như sau: ~[4 \ 2 \ 1 \ 5 \ 9 \ 8 \ 7 \ 6 \ 3]~ và ~[10]~.