QNT và Haky đang giúp anh Domixi bán khô gà bã mía – một công việc phức tạp mà chỉ khi hát bài Nà ná na thì mới xong được .

Hai anh em quyết định tâm là kết hợp với nhau: QNT sẽ đóng bã mía, còn Haky sẽ đè tem. QNT được giao một vài đống bã mía đánh số từ ~1~ đến ~N~ (~1 \le N \le 10^5~). Haky có một bộ tem – Sử dụng để đóng lên các hộp khô gà. Giữa QNT và Haky có một mặt bàn để đặt các hộp đã đóng bã mía.

Ở mỗi bước, một trong hai việc sau sẽ xảy ra:

• QNT: Lấy một bã mía từ đống bã mía, bôi phẩm màu và gia vị, rồi đặt lên mặt bàn làm thành hộp khô gà. Khi đặt bã mía đã chế biến, QNT phải hoặc (i) đặt khô gà lên trên một chồng khô gà không rỗng đã có, hoặc (ii) tạo một chồng khô gà mới ở bên phải tất cả các chồng khô gà hiện tại.
• Haky: Lấy một bịch khô gà từ đỉnh của chồng khô gà ngoài cùng bên trái. Haky đè tem, rồi đặt lên trên chồng sản phẩm cuối.

Mục tiêu là chồng sản phẩm cuối chứa toàn bộ khô gà theo thứ tự: Số nhỏ nhất ở dưới cùng và số lớn nhất ở trên cùng. Có thể không thể đạt được mục tiêu này cho toàn bộ chồng đĩa, vậy hãy xác định độ dài tiền tố dài nhất của thứ tự đầu vào sao cho mục tiêu vẫn có thể đạt được.

Input

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~).

~N~ dòng tiếp theo mô tả thứ tự các bịch bã mía trong chồng khô gà của QNT, trong đó số đầu tiên là bịch ở đỉnh chồng.

Output

In ra độ dài tiền tố dài nhất của chồng khô gà đầu vào có thể được xử lý thành công sao cho các bịch khô gà kết thúc được sắp xếp đúng thứ tự trong chồng sản phẩm cuối.

Example

Input

5
4
5
2
3                                                                                                                                                                                               
1

Output

4