Đầy tham vọng, Farmer John định thử một việc dường như chẳng bao giờ thành công hoàn toàn: chụp ảnh cả đàn bò.

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

Farmer John muốn đổi chỗ từng cặp bò để cả đàn lại đúng thứ tự. Hãy giúp ông tìm số lần đổi chỗ nhỏ nhất cần thực hiện.

Dữ liệu vào

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

Dữ liệu ra

In số lần đổi chỗ cặp bò nhỏ nhất để đạt thứ tự đúng. Hai con bò được đổi không nhất thiết phải đứng cạnh nhau.

Ví dụ

Dữ liệu vào 1

6
2
4
7
7
9
3

Dữ liệu ra 1

3

Ghi chú

Trong ví dụ này, Bessie rõ ràng là con bò cao 3. FJ khôi phục thứ tự bằng ba lần đổi dưới đây:

2 4 7 7 9 3 - Hàng ban đầu
2 4 7 7 3 9 - Đổi hai con bò cuối
2 4 3 7 7 9 - Đổi số 7 đầu tiên và 3
2 3 4 7 7 9 - Đổi 4 và 3

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