Bạn được cho một dãy gồm các số nguyên phân biệt \(A = [A_1, A_2, ..., A_N]\), và muốn sắp xếp lại nó thành một dãy lên và xuống (một dãy mà \(A_1 < A_2 < ... < A_m > A_{m+1} > ... > A_N\) với một chỉ số \(m\) nào đó, \(m\) nằm trong khoảng từ \(1\) đến \(N\) bao gồm cả hai đầu).

Việc sắp xếp lại được thực hiện bằng cách hoán đổi hai phần tử kề nhau của dãy tại một thời điểm. Như dự đoán, bạn đặc biệt quan tâm đến số lượng hoán đổi ít nhất cần thiết để đạt được một dãy lên và xuống.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất: \(N\). Dòng tiếp theo chứa \(N\) số nguyên phân biệt: \(A_1, ..., A_N\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng hoán đổi tối thiểu cần thiết để sắp xếp lại \(A\) thành một dãy lên và xuống.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le A_i \le 10^9\).
• Các \(A_i\) sẽ đôi một phân biệt.

Phân nhóm

• Small dataset: \(1 \le N \le 10\).
• Large dataset: \(1 \le N \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3
1 2 3
5
1 8 10 3 7

Case #1: 0
Case #2: 1

Nguồn

Google Code Jam 2014, Vòng 2, bài Up and Down.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.