Mô tả và yêu cầu

PERGAME
Xét trò chơi sắp xếp trên hoán vị như sau: Máy tính tạo ngẫu nhiên một hoán vị 𝑝1, 𝑝2, … ,𝑝𝑛 của
1,2,… ,𝑛 (𝑛 chẵn). Nhiệm vụ của người chơi là thực hiện ít thao tác đổi chỗ hai phần tử bất kì nhất
để nhận được hoán vị có điểm cao nhất. Điểm của một hoán vị 𝑝1, 𝑝2, … ,𝑝𝑛 được tính
∑𝑛−1 |𝑝𝑖 − 𝑝𝑖+1|
𝑖=1

Dữ liệu vào

- Dòng đầu chứa số nguyên 𝑛;
- Dòng tiếp theo chứa 𝑛 số nguyên mô tả hoán vị 𝑝1, 𝑝2, … ,𝑝𝑛.

Dữ liệu ra

- Gồm một số là số thao tác cần thực hiện.
PERGAME.INP PERGAME.OUT
4 3
1 2 3 4

Subtask 1: 𝑛 ≤ 8;
Subtask 2: 𝑛 ≤ 16;
Subtask 3: 𝑛 ≤ 168;