Hôm nay là sinh nhật của Byteman. Có \(n\) bạn nhỏ tham dự bữa tiệc, kể cả Byteman, được đánh số từ \(1\) đến \(n\). Bố mẹ Byteman đã chuẩn bị một chiếc bàn tròn lớn và đặt \(n\) chiếc ghế xung quanh. Khi đến dự tiệc, các bạn lần lượt ngồi xuống: bạn số \(1\) chọn một ghế, bạn số \(2\) ngồi vào ghế bên trái bạn số \(1\), bạn số \(3\) ngồi vào ghế tiếp theo bên trái, và cứ như vậy. Cuối cùng, bạn số \(n\) ngồi vào chiếc ghế trống còn lại, giữa bạn số \(1\) và bạn số \(n-1\).

Bố mẹ Byteman hiểu rất rõ các bạn nhỏ và biết rằng một số bạn sẽ gây ồn ào nếu ngồi quá gần nhau. Vì vậy, họ muốn sắp xếp lại chỗ ngồi theo một thứ tự nhất định. Thứ tự đó được mô tả bằng một hoán vị \(p_1,p_2,\ldots,p_n\) của các số từ \(1\) đến \(n\): bạn \(p_1\) phải ngồi giữa \(p_n\) và \(p_2\); bạn \(p_i\), với \(i=2,3,\ldots,n-1\), phải ngồi giữa \(p_{i-1}\) và \(p_{i+1}\); còn bạn \(p_n\) phải ngồi giữa \(p_{n-1}\) và \(p_1\). Lưu ý rằng bạn \(p_1\) có thể ngồi bên trái hoặc bên phải bạn \(p_n\).

Để đưa các bạn về đúng thứ tự, bố mẹ Byteman phải cho mỗi bạn di chuyển quanh bàn sang trái hoặc sang phải một số ghế. Với từng bạn, họ phải chọn cả hướng di chuyển và khoảng cách di chuyển, tính bằng số ghế. Khi có hiệu lệnh, tất cả các bạn cùng đứng dậy, di chuyển đến vị trí của mình rồi ngồi xuống.

Việc đổi chỗ làm bữa tiệc trở nên lộn xộn. Mức độ lộn xộn bằng khoảng cách lớn nhất mà một bạn phải di chuyển. Có nhiều cách sắp xếp lại chỗ ngồi, và bố mẹ Byteman muốn chọn cách có mức độ lộn xộn nhỏ nhất.

Cho số bạn nhỏ và hoán vị mô tả thứ tự mong muốn, hãy viết chương trình tìm mức độ lộn xộn nhỏ nhất có thể.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa một số nguyên \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\), cách nhau bởi một dấu cách. Các số này tạo thành một hoán vị của tập \(\{1,2,\ldots,n\}\), mô tả thứ tự chỗ ngồi mong muốn.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: mức độ lộn xộn nhỏ nhất có thể.

Ràng buộc

• \(1 \le n \le 1\,000\,000\).
• \(1 \le p_i \le n\) với \(1 \le i \le n\); các giá trị \(p_i\) đôi một khác nhau.

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\) không vượt quá \(1\,000\).

Ví dụ

6
3 4 5 1 2 6

2

Nguồn

IOI 2005, ngày thi thứ hai: Birthday, bản tiếng Anh 1.02. Tác giả đề bài: Jakub Pawlewicz. Tập đề bài và lời giải IOI 2005.