Rửa bát

Bessie và Elsie cùng rửa bát. Có $N$ chiếc đĩa bẩn xếp thành một chồng, kích thước của chúng đôi một khác nhau và tạo thành một hoán vị của $1,2,\dots ,N$. Đĩa thứ $i$ tính từ trên xuống có kích thước $p_i$.

Trên quầy bếp có một dãy các chồng đĩa đã rửa xà phòng, xếp từ trái sang phải (ban đầu chưa có chồng nào). Hai con bò làm việc như sau, và có thể xen kẽ thao tác của mình theo thứ tự bất kỳ:

• Bessie lấy chiếc đĩa trên cùng của chồng đĩa bẩn, rửa xà phòng, rồi đặt nó lên quầy. Cô chỉ được đặt chiếc đĩa đó lên trên một chồng đang có mà đĩa trên cùng của chồng ấy lớn hơn chiếc đĩa vừa rửa, hoặc tạo một chồng mới nằm bên phải tất cả các chồng hiện có.
• Elsie lấy chiếc đĩa trên cùng của chồng bên trái nhất (trong các chồng còn đĩa) trên quầy, tráng nước, rồi đặt sang chồng đĩa sạch. Chồng đĩa sạch phải có kích thước tăng dần, nghĩa là mỗi chiếc đĩa Elsie tráng phải lớn hơn mọi chiếc đĩa cô đã tráng trước đó.

Hai người muốn xử lý xong càng nhiều đĩa càng tốt, tính từ trên chồng đĩa bẩn xuống. Hãy tìm số $K$ lớn nhất sao cho $K$ chiếc đĩa đầu tiên đều có thể được rửa xà phòng rồi tráng nước xong (những chiếc đĩa còn lại không được đụng tới).

Dữ liệu vào

• Dòng đầu chứa số nguyên $N$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $p_i$, là kích thước của chiếc đĩa thứ $i$ tính từ trên chồng đĩa bẩn xuống.

Dữ liệu ra

Một số nguyên duy nhất: giá trị $K$ lớn nhất.

Ràng buộc

• $1\le N\le {10}^5$
• $p_1,p_2,\dots ,p_N$ là một hoán vị của $1,2,\dots ,N$

Ví dụ