Vào ngày cuối của một trại huấn luyện, \(N\) người tham gia sẽ chụp ảnh tập thể. Họ được đánh số từ \(1\) đến \(N\) theo thứ tự chiều cao tăng dần. Chiều cao của người thứ \(h\) là \(h\) (\(1 \le h \le N\)).

Mọi người đứng trên một cầu thang để chụp ảnh. Cầu thang có đúng \(N\) bậc, đánh số từ \(1\) đến \(N\) từ thấp lên cao. Bậc \(i+1\) cao hơn bậc \(i\) đúng \(2\) đơn vị (\(1 \le i < N\)). Cầu thang rất hẹp nên mỗi bậc chỉ có một người đứng, tạo thành một hàng dọc.

Buổi chụp ảnh sắp bắt đầu. Hiện tại, người thứ \(H_i\) đang đứng trên bậc \(i\) (\(1 \le i \le N\)).

Do chiều cao của mọi người chênh lệch nhiều, một số người có thể bị người khác che khuất trong ảnh. Bạn muốn sắp xếp lại vị trí để ít nhất phần đỉnh đầu của mọi người đều xuất hiện trong ảnh. Cụ thể, cần thỏa mãn điều kiện:

• Gọi \(a_i\) là chiều cao của người đứng trên bậc \(i\). Khi đó, \(a_i < a_{i+1}+2\) với mọi \(1 \le i < N\).

Bạn chỉ được đổi chỗ hai người đứng ở hai bậc liên tiếp. Trong một thao tác, chọn một bậc \(i\) (\(1 \le i < N\)), rồi đổi chỗ người trên bậc \(i\) với người trên bậc \(i+1\).

Cho thứ tự hiện tại của mọi người, hãy tìm số thao tác ít nhất để thỏa mãn điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

N
H_1 H_2 ... H_N

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất cần thực hiện.

Ràng buộc

• \(3 \le N \le 5000\).
• \(1 \le H_i \le N\) với mọi \(1 \le i \le N\).
• \(H_i \ne H_j\) với mọi \(1 \le i < j \le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 9\).
• Nhóm 2 (7 điểm): \(N \le 20\).
• Nhóm 3 (32 điểm): \(N \le 200\).
• Nhóm 4 (20 điểm): \(N \le 800\).
• Nhóm 5 (36 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
3 5 2 4 1

3

5
3 2 1 5 4

0

9
6 1 3 4 9 5 7 8 2

9

Nguồn

JOI 2020/2021, vòng chung kết quốc gia, ngày 14/02/2021. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Anh, tiếng Nhật. Bản dịch theo giấy phép CC BY-SA 4.0.