Với đầy tham vọng, bác nông dân John dự định thử làm một việc dường như chẳng bao giờ diễn ra suôn sẻ: ông muốn chụp ảnh toàn bộ đàn bò của mình.

Để bức ảnh trông đẹp mắt, ông muốn các cô bò xếp thành một hàng từ thấp nhất đến cao nhất. Không may, ngay sau khi ông xếp đàn bò theo thứ tự này, cô bò Bessie vốn luôn gây rắc rối lại bước ra khỏi hàng rồi chen vào một vị trí khác trong hàng!

Bác nông dân John muốn hoán đổi từng cặp bò để cả đàn một lần nữa được xếp đúng thứ tự. Hãy giúp ông xác định số lần hoán đổi ít nhất giữa các cặp bò để đạt được mục tiêu này.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(2 \leq N \leq 100\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả chiều cao của một cô bò theo thứ tự trong hàng sau khi Bessie di chuyển. Chiều cao của mỗi cô bò là một số nguyên trong khoảng \(1 \ldots 1{,}000{,}000\). Nhiều cô bò có thể có cùng chiều cao.

Dữ liệu ra

In ra số lần ít nhất bác nông dân John cần hoán đổi các cặp bò để đưa đàn bò về đúng thứ tự. Các lần hoán đổi không nhất thiết phải thực hiện giữa hai cô bò đứng kề nhau trong hàng.

Ví dụ

6
2
4
7
7
9
3

3

2 4 7 7 9 3 - Hàng ban đầu
2 4 7 7 3 9 - Hoán đổi hai cô bò cuối cùng
2 4 3 7 7 9 - Hoán đổi cô bò 7 đầu tiên với cô bò 3
2 3 4 7 7 9 - Hoán đổi cô bò 4 với cô bò 3

Nguồn

USACO 2018 January Contest, Bronze — Out of Place

Tác giả bài toán: Brian Dean.