Câu 3: Hộp quà (5.0 điểm)

Có \(n\) hộp quà, các hộp quà được đánh số từ \(1\) đến \(n\), hộp thứ \(i\) có giá trị \(a_i\) (\(1 \le a_i \le m\)). Lớp Nam được giao nhiệm vụ chuẩn bị \(K\) giỏ quà từ \(n\) hộp quà đã có, tuân thủ tất cả các quy tắc sau:

• Mỗi giỏ quà gồm hai hộp quà;
• Hộp quà thứ nhất được lấy từ các hộp quà có chỉ số từ \(1\) đến \(K\), hộp quà thứ hai được lấy từ các hộp quà có chỉ số từ \(K + 1\) đến \(n\);
• Giá trị hộp quà thứ nhất nhỏ hơn giá trị hộp quà thứ hai.

Ví dụ: Cho các hộp quà có giá trị: \(2\) \(1\) \(4\) \(2\) \(3\) \(2\) \(4\) \(5\) \(2\) \(3\) Nam có thể ghép được \(4\) hộp quà có giá trị \(2\) \(1\) \(4\) \(2\) với \(6\) hộp quà có giá trị \(3\) \(2\) \(4\) \(5\) \(2\) \(3\) tạo thành \(4\) giỏ quà được ghép là \(\{(2, 3), (1, 2), (4, 5), (2, 3)\}\) hoặc \(\{(2, 3), (1, 2), (4, 5), (2, 4)\}\).

Yêu cầu: Cho \(n\) hộp quà có giá trị \(a_1, a_2, a_3, ..., a_n\), hãy tìm \(K\) lớn nhất theo quy tắc trên.

Input

Vào từ tệp văn bản CAU3.INP có cấu trúc:

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) \((1 \leq n \leq 10^5, 1 \leq m \leq 10^9)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le m\)).

Output

Ghi ra tệp văn bản CAU3.OUT là số \(K\) lớn nhất tìm được, nếu không có nghiệm thì in ra \(-1\).

Example

10 5
2 1 4 2 3 2 4 5 2 3

4

5 6
5 4 2 1 2

-1

Scoring

• Subtask \(1\) (\(2,0\) điểm): \(1 \leq n \leq 100, 1 \leq m \leq 10^3\).
• Subtask \(2\) (\(1,5\) điểm): \(100 \leq n \leq 5 \times 10^3, 1 \leq m \leq 10^9\)
• Subtask \(3\) (\(1,5\) điểm): không có ràng buộc gì thêm.