Farmer John đang cố gắng sắp xếp \(N\) con bò của mình (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \dots N\), trước khi chúng ra đồng cỏ ăn sáng.

Hiện tại, các cô bò đang đứng thành một hàng theo thứ tự \(p_1, p_2, p_3, \dots, p_N\), còn Farmer John đứng trước cô bò \(p_1\). Ông muốn sắp xếp lại để các cô bò có thứ tự \(1, 2, 3, \dots, N\), trong đó cô bò \(1\) đứng cạnh Farmer John.

Hôm nay các cô bò hơi buồn ngủ, nên tại bất kỳ thời điểm nào, cô bò duy nhất chú ý đến chỉ dẫn của Farmer John là cô đứng ngay trước mặt ông. Trong một bước thời gian, ông có thể yêu cầu cô bò này di chuyển xuống dưới hàng \(k\) vị trí, với \(k\) bất kỳ từ \(1\) đến \(N-1\), kể cả hai đầu mút. \(k\) cô bò mà cô ấy đi qua sẽ chậm rãi tiến lên phía trước, tạo chỗ để cô ấy chen vào hàng ngay sau họ.

Ví dụ, giả sử \(N=4\) và ban đầu các cô bò đứng theo thứ tự sau:

FJ: 4, 3, 2, 1

Cô bò duy nhất đang chú ý đến FJ là cô bò \(4\). Nếu ông yêu cầu cô ấy di chuyển xuống dưới hàng \(2\) vị trí, thứ tự sau đó sẽ là:

FJ: 3, 2, 4, 1

Lúc này cô bò duy nhất đang chú ý đến FJ là cô bò \(3\), nên ở bước thời gian thứ hai ông có thể đưa ra chỉ dẫn cho cô bò \(3\), và cứ tiếp tục như vậy cho đến khi các cô bò được sắp xếp xong.

Farmer John nóng lòng hoàn thành việc sắp xếp để có thể trở về trang trại ăn sáng. Hãy giúp ông tìm một dãy chỉ dẫn sắp xếp các cô bò trong số bước thời gian tối thiểu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách: \(p_1, p_2, p_3, \dots, p_N\), cho biết thứ tự ban đầu của các cô bò.

Dữ liệu ra

Dòng đầu tiên chứa một số nguyên duy nhất \(K\), là số bước thời gian tối thiểu cần thiết để sắp xếp các cô bò.

Dòng thứ hai chứa \(K\) số nguyên cách nhau bởi dấu cách, \(c_1, c_2, \dots, c_K\), mỗi số thuộc khoảng \(1 \ldots N-1\). Hơn nữa, nếu ở bước thời gian thứ \(i\), FJ yêu cầu cô bò đứng trước mặt mình di chuyển xuống dưới hàng \(c_i\) vị trí, thì sau \(K\) bước thời gian, các cô bò phải ở đúng thứ tự.

Nếu có nhiều dãy chỉ dẫn tối ưu, chương trình có thể in ra bất kỳ dãy nào trong số đó.

Ví dụ

4
1 2 4 3

3
2 2 3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Gold — Sleepy Cow Sorting

Tác giả: Dhruv Rohatgi