Thu Bài Thi
Xem dạng PDFKỳ thi tuyển sinh lớp 10 vừa kết thúc, ~N~ thí sinh đã nộp bài thành một xấp. Các bài thi có số báo danh từ ~1~ đến ~N~, mỗi số xuất hiện đúng một lần. Theo quy chế, bài thi phải được cho vào túi niêm phong theo đúng thứ tự: bài có số báo danh nhỏ nhất nằm dưới đáy túi, bài có số báo danh lớn nhất nằm trên cùng.
Việc xếp bài được giao cho hai giám thị là thầy Quân và thầy Trọng. Thầy Trọng ngồi ở đầu bàn bên trái, ngay cạnh túi niêm phong, và vì đã ngồi canh thi suốt ba tiếng nên thầy nhất quyết không đứng dậy. Thầy Quân cầm xấp bài vừa thu trên tay, đứng ở đầu bên kia và xếp tạm bài thành các chồng dọc theo mặt bàn.
Ở mỗi bước, một trong hai việc sau được thực hiện:
Thầy Quân lấy bài trên cùng của xấp bài vừa thu, kiểm tra chữ ký rồi đặt lên bàn theo một trong hai cách: đặt lên trên một chồng bài đang có trên bàn, 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ó.
Thầy Trọng lấy bài trên cùng của chồng ngoài cùng bên trái và cho vào túi niêm phong, nằm trên tất cả các bài đã có trong túi. Nếu chồng đó hết bài, nó biến mất khỏi bàn.
Hai thầy được tự do chọn thứ tự thực hiện các bước.
Tất nhiên, không phải lúc nào hai thầy cũng xếp được cả ~N~ bài. Khi đó, hai thầy sẽ chỉ xử lý một số bài trên cùng của xấp bài vừa thu, còn những bài bên dưới để nguyên và giao lại cho hội đồng thi.
Hai thầy muốn xử lý được càng nhiều bài càng tốt. Hãy tìm số ~k~ lớn nhất sao cho hai thầy có thể cho hết ~k~ bài trên cùng vào túi, sao cho số báo danh tăng dần từ đáy túi lên trên.
Input
Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~).
Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là một hoán vị của ~1, 2, \ldots, N~, trong đó ~a_1~ là số báo danh của bài nằm trên cùng xấp bài vừa thu.
Output
In ra số nguyên ~k~ lớn nhất thỏa mãn.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~N \le 10~ |
| 2 | ~30~ | ~N \le 5000~ |
| 3 | ~50~ | Không có ràng buộc gì thêm |
Sample Input 1
5
4 5 2 3 1
Sample Output 1
4
Sample Input 2
4
3 4 1 2
Sample Output 2
4
Notes
Giải thích ví dụ 1. Thầy Quân đặt bài ~4~ (chồng mới), bài ~5~ (chồng mới bên phải), rồi bài ~2~ lên trên bài ~4~. Thầy Trọng cho bài ~2~ vào túi. Thầy Quân đặt bài ~3~ lên trên bài ~4~. Thầy Trọng lần lượt cho bài ~3, 4, 5~ vào túi. Túi chứa ~2, 3, 4, 5~ (từ dưới lên), đúng thứ tự. Không thể xếp thêm bài ~1~ vì bài ~2~ đã nằm trong túi, nên hai thầy xử lý ~4~ bài trên cùng và bài ~1~ được giao lại cho hội đồng thi.
Trong các bảng dưới đây, mỗi chồng trên bàn và túi niêm phong đều được ghi từ dưới lên.
| Lượt | Người | Thao tác | Các chồng trên bàn (trái sang phải) | Túi niêm phong |
|---|---|---|---|---|
| 1 | Thầy Quân | Đặt bài ~4~ thành chồng mới | ~[4]~ | (trống) |
| 2 | Thầy Quân | Đặt bài ~5~ thành chồng mới | ~[4]~ ~[5]~ | (trống) |
| 3 | Thầy Quân | Đặt bài ~2~ lên chồng thứ nhất | ~[4, 2]~ ~[5]~ | (trống) |
| 4 | Thầy Trọng | Cho bài ~2~ vào túi | ~[4]~ ~[5]~ | ~2~ |
| 5 | Thầy Quân | Đặt bài ~3~ lên chồng thứ nhất | ~[4, 3]~ ~[5]~ | ~2~ |
| 6 | Thầy Trọng | Cho bài ~3~ vào túi | ~[4]~ ~[5]~ | ~2, 3~ |
| 7 | Thầy Trọng | Cho bài ~4~ vào túi | ~[5]~ | ~2, 3, 4~ |
| 8 | Thầy Trọng | Cho bài ~5~ vào túi | (trống) | ~2, 3, 4, 5~ |
Giải thích ví dụ 2. Thầy Quân đặt bài ~3~ (chồng mới), bài ~4~ (chồng mới bên phải), rồi bài ~1~ lên trên bài ~3~. Thầy Trọng cho bài ~1~ vào túi. Thầy Quân đặt bài ~2~ lên trên bài ~3~. Thầy Trọng lần lượt cho bài ~2, 3, 4~ vào túi. Túi chứa ~1, 2, 3, 4~ (từ dưới lên), đúng thứ tự, nên hai thầy xử lý được cả ~4~ bài. Lưu ý nếu chỉ dùng một chồng trên bàn, bài ~3~ phải được cho vào túi trước khi đặt bài ~4~, khi đó bài ~1~ sẽ không thể xếp được nữa.
| Lượt | Người | Thao tác | Các chồng trên bàn (trái sang phải) | Túi niêm phong |
|---|---|---|---|---|
| 1 | Thầy Quân | Đặt bài ~3~ thành chồng mới | ~[3]~ | (trống) |
| 2 | Thầy Quân | Đặt bài ~4~ thành chồng mới | ~[3]~ ~[4]~ | (trống) |
| 3 | Thầy Quân | Đặt bài ~1~ lên chồng thứ nhất | ~[3, 1]~ ~[4]~ | (trống) |
| 4 | Thầy Trọng | Cho bài ~1~ vào túi | ~[3]~ ~[4]~ | ~1~ |
| 5 | Thầy Quân | Đặt bài ~2~ lên chồng thứ nhất | ~[3, 2]~ ~[4]~ | ~1~ |
| 6 | Thầy Trọng | Cho bài ~2~ vào túi | ~[3]~ ~[4]~ | ~1, 2~ |
| 7 | Thầy Trọng | Cho bài ~3~ vào túi | ~[4]~ | ~1, 2, 3~ |
| 8 | Thầy Trọng | Cho bài ~4~ vào túi | (trống) | ~1, 2, 3, 4~ |