Farmer John muốn ảnh cả đàn $N$ bò, $1 \le N \le 100,000$, số $1..N$, để khoe bạn.

Ngày chụp ảnh bò chạy thành hàng tùy ý, vị trí $i$ là $c_{i}$, $1 \le c_{i} \le N$. Ông có ý về thứ tự.

FJ nghĩ rằng Bò $i$ chỉ bên trái $i+1$ với mọi $i$, $1 \le i \le N-1$, và $N$ chỉ trái bò $1$. Tất nhiên không bò nào trái bò đầu, ngoài cùng trái.

Đói đợi bữa tối hứa sau ảnh, ông muốn nhanh. Bò không giỏi theo lệnh, chỉ chọn cặp kề đổi một lần mỗi phút. Bao lâu tới thứ tự chấp nhận được?

Ví dụ năm bò ban đầu:

     Trái           Phải
        3  5  4  2  1

Đổi cặp thứ hai trước:

        3  4  5  2 1

Rồi cặp ngoài cùng phải:

        3  4  5  1  2

Thứ tự hợp lệ chỉ cần hai phút đổi.

Dữ liệu vào

• Dòng $1$: một số nguyên $N$.

• Các dòng $2..N+1$: dòng $i+1$ mã bò thứ $i$, $c_{i}$.

Dữ liệu ra

• Dòng $1$: thời gian nhỏ nhất theo phút tới thứ tự phù hợp.

Ví dụ

Dữ liệu vào 1

5
3
5
4
2
1

Dữ liệu ra 1

2

Ghi chú

Tác giả bài toán: Travis, 2010