Phong là một học sinh rất say mê các hoạt động STEM và rất thích thực hiện những thí nghiệm thực tế. Trong một lần thí nghiệm, Phong đã đo nhiệt độ trung bình trong ~N~ ngày liên tiếp và được các kết quả là các số thực đôi một khác nhau. Phong chuyển các kết quả này thành một dãy gồm các số nguyên từ ~1~ đến ~N~, mỗi số xuất hiện đúng một lần. Số ở ngày thứ ~i~ là ~A_i~, cho biết rằng trong ~N~ ngày mà Phong thực hiện thí nghiệm có đúng ~A_i-1~ ngày mà nhiệt độ đo được thấp hơn nhiệt độ ở ngày thứ ~i~.

Tiếp theo, Phong thực hiện các bước tách nhóm dữ liệu. Với mỗi bước, Phong sẽ tìm ngày có nhiệt độ cao nhất và ngày có nhiệt độ thấp nhất trong dãy, sau đó tách dữ liệu nhiệt độ của các ngày nằm trong đoạn giữa hai ngày này (kể cả hai ngày có nhiệt độ cao nhất và thấp nhất) thành một nhóm, và nối dữ liệu của các ngày còn lại thành một dãy mới (giữ nguyên thứ tự). Phong lặp lại quy trình này trên dãy mới cho đến khi dãy này trở thành dãy rỗng và đếm số nhóm đã tách được.

Yêu cầu: Vì dữ liệu gồm rất nhiều ngày nên việc tính toán bằng tay có thể mất rất nhiều thời gian, Phong muốn viết một chương trình tính nhanh số nhóm mà Phong tách được. Hãy giúp Phong tính toán thông tin này.

Input

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(1 \le N \le 2 \times 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

• Một số duy nhất là số nhóm mà Phong tách được.

Scoring

Sample Input 1

6
3 5 1 4 6 2

Sample Output 1

3

Sample Input 2

7
1 6 2 7 3 4 5

Sample Output 2

2

Notes

Ví dụ thứ nhất:

• Trong thao tác tách nhóm đầu tiên, ngày có nhiệt độ cao nhất là ngày thứ ~5~, thấp nhất là ngày thứ ~3~. Phong tách được nhóm ~[1,4,6]~ và dãy còn lại là ~[3,5,2]~.

• Trong thao tác tiếp theo, Phong tách được nhóm ~[5,2]~ và dãy còn lại là ~[3]~.

• Trong thao tác cuối cùng, Phong tách được nhóm ~[3]~ và dãy còn lại là dãy rỗng.

Ví dụ thứ hai:

• Thao tác đầu tiên, Phong tách được nhóm ~[1,6,2,7]~. Dãy còn lại là ~[3,4,5]~.

• Thao tác thứ hai, Phong tách được nhóm ~[3,4,5]~. Dãy còn lại là dãy rỗng.