Thái có một hàng gồm \(n\) cuốn sách, mỗi cuốn được đánh số từ \(1\) đến \(n\), nhưng hiện tại chúng đang nằm trong một thứ tự ngẫu nhiên trên kệ. Mỗi lần di chuyển, Thái có thể chọn hai cuốn sách đứng cạnh nhau và đổi chỗ chúng. Mục tiêu của Thái là sắp xếp lại các cuốn sách theo thứ tự tăng dần từ \(1\) đến \(n\).

Nhiệm vụ của Thái là tìm số lần đổi chỗ ít nhất cần thực hiện để sắp xếp các cuốn sách theo đúng thứ tự.

Giả sử dãy cuốn sách ban đầu là [3,1,2], Thái cần sắp xếp lại dãy này thành [1,2,3].

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên \(n\) \((1 \le n \le 10^5)\)
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Dữ liệu ra

• In ra số lượng thao tác ít nhất.

Input 1

4
2 4 1 3

Output 1

3

Input 2

7
1 4 3 5 2 6 7

Output 2

4