Sau bữa tiệc sinh nhật, hai anh em An và Bình được giao rửa một chồng đĩa gồm \(N\) chiếc đĩa được đánh số \(1, 2, \dots, N\). An đứng ở bồn rửa \(1\) với chồng đĩa bẩn, Bình đứng ở bồn rửa \(2\) và chờ để tráng đĩa bằng nước. Ở giữa An và Bình có một quầy để xếp những chiếc đĩa đã có xà phòng và chờ tráng nước. Ở mỗi bước, một trong hai thao tác sau cần thực hiện:

• An lấy chiếc đĩa trên cùng của chồng đĩa bẩn. Làm sạch bằng xà phòng. Sau đó xếp chiếc đĩa này vào quầy chờ tráng nước bằng một trong hai cách:
  • Xếp vào một chồng đĩa đã có trước đó trên quầy
  • Tạo một chồng đĩa mới nằm bên phải những chồng đã có trước đó.
• Bình lấy chiếc đĩa trên cùng của chồng đĩa nằm bên trái cùng của quầy chờ. Tráng bằng nước, rồi xếp lên trên cùng của chồng đĩa sạch.

Thứ tự của những chiếc đĩa rất quan trọng. Do đó mục tiêu của An và Bình là chồng đĩa sạch phải được xếp theo nguyên tắc: đĩa có số thứ tự nhỏ nằm ở dưới, đĩa có số thứ tự lớn nằm ở trên. Tuy nhiên, điều kiện này có thể không hoàn thành được cho toàn bộ \(N\) chiếc đĩa. Vậy nên, bạn hãy giúp An và Bình xác định độ dài tiền tố tối đa của chồng đĩa có thể thỏa mãn điều kiện này.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 10^5)\)
• \(N\) dòng tiếp theo cho biết số thứ tự của các chiếc đĩa trong chồng đĩa bẩn theo chiều từ trên xuống.

Output

• In ra độ dài tiền tố lớn của chồng đĩa sao cho các đĩa sau khi rửa sạch có thể được xếp theo đúng thứ tự.

Examples

5
4
5
2
3
1

4