Trong kho của một nhà máy có rất nhiều thùng rỗng xếp thành một hàng. Người quản lý muốn đặt một số thùng vào trong các thùng khác để tạo khoảng trống ở đầu bên trái của kho. Robot có thể nhấc một thùng, mang nó sang phải rồi đặt vào một thùng lớn hơn. Chuỗi ba thao tác này là cách duy nhất được phép dùng để di chuyển thùng.

Theo quy định an toàn, mỗi thùng chỉ được chứa nhiều nhất một thùng khác, và thùng được chứa phải rỗng. Người quản lý cũng muốn những cặp thùng lồng vào nhau nằm ở đầu bên trái của hàng còn lại để dễ theo dõi.

Hãy tìm số nguyên \(K\) lớn nhất sao cho có thể đặt \(K\) thùng ngoài cùng bên trái vào \(K\) thùng ngay tiếp theo, theo một thứ tự nào đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(M\) và \(N\), lần lượt là kích thước thùng lớn nhất và số thùng. Dòng thứ hai chứa \(N\) số nguyên \(A_i\), là kích thước các thùng theo thứ tự từ trái sang phải.

Dữ liệu ra

In một số nguyên là giá trị lớn nhất của \(K\) sao cho robot có thể đặt \(K\) thùng đầu tiên vào \(K\) thùng ngay tiếp theo.

Ràng buộc

• \(1 \le M \le 1000\).
• \(1 \le N \le 20\,000\).
• \(1 \le A_i \le M\) với \(1 \le i \le N\).

Ví dụ

5 10
2 2 1 4 3 2 5 4 2 3

4