Ngày xửa ngày xưa, trong một vương quốc xa xôi, có một vị vua nổi tiếng về tính kiên nhẫn và trí tuệ. Một ngày nọ, nhà vua quyết định tổ chức một cuộc thi để tìm kiếm người kế vị xứng đáng. Cuộc thi này không chỉ đòi hỏi sức mạnh mà còn đòi hỏi trí tuệ và sự kiên nhẫn.

Nhà vua triệu tập tất cả các thanh niên trong vương quốc và đưa cho họ một nhiệm vụ tưởng chừng như đơn giản nhưng vô cùng thách thức. Ngài trao cho mỗi người một chiếc rương chứa các viên ngọc đánh số từ 1 đến \(n\), nhưng chúng được sắp xếp một cách lộn xộn.

"Nhiệm vụ của các ngươi là thu thập các viên ngọc theo thứ tự từ 1 đến \(n\) theo đúng thứ tự tăng dần. Các ngươi phải làm việc này qua nhiều vòng, mỗi vòng các ngươi đi qua rương từ trái sang phải và thu thập được nhiều viên ngọc nhất có thể theo thứ tự tăng dần.", nhà vua tuyên bố.

Nhà vua biết rằng thử thách này sẽ đòi hỏi sự thông minh và khả năng lập kế hoạch của các thí sinh. Ngài hứa rằng người nào hoàn thành nhiệm vụ với số vòng ít nhất sẽ được chọn làm người kế vị. Trong số các thí sinh tham gia, có một chàng trai trẻ có biệt danh là Giáo sư Hòa, nổi tiếng về sự thông minh và khéo léo. Hòa hoàn toàn có thể giải thử thách một cách dễ dàng, thế nhưng hiện tại, Hòa đang bận đi healing sau khoảng thời gian ôn thi vất vả. Hòa muốn nhờ bạn giải quyết thử thách của nhà vua.

Input

• Dòng đầu tiên chứa một số nguyên \(n (1 \leq n \leq 2 \times 10^5)\): kích thước của mảng.
• Dòng thứ hai chứa n số nguyên \(( x_1, x_2, …, x_n )\): các số trong mảng.

Output

• In ra một số nguyên: số vòng lặp cần thiết để thu thập tất cả các viên ngọc theo thứ tự tăng dần.

Scoring

• 50% số test \(n \leq 10^4\).
• 50% số test còn lại không có ràng buộc gì thêm.

Example

5
4 2 1 5 3

3

7
2 4 5 3 1 7 6

4