Farmer John đang cố gắng sắp xếp \(N\) con bò của mình (\(1 \leq N \leq 100\)), đượ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ỳ trong khoảng \(1 \ldots N-1\). \(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 số bước thời gian tối thiểu cần thiết để sắp xếp các cô bò.

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

In ra một số nguyên duy nhất: số bước thời gian trước khi \(N\) con bò được xếp theo đúng thứ tự, nếu Farmer John hành động tối ưu.

Ví dụ

4
1 2 4 3

3

Nguồn

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

Tác giả: Dhruv Rohatgi