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 cô giáo 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ứ 2 được lấy từ các hộp quà có chỉ số từ \(K+1\) đến \(n\);
• Hộp quà thứ nhất có giá trị nhỏ hơn hộp quà thứ 2.

Ví dụ: Cho các hộp quà có giá trị lần lượt như sau: 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)\}\).

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

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m\) (\(1 \le n \le 10^5, 1 \le m \le 10^9\));
• Dòng tiếp theo ghi \(n\) số nguyên dương \(a_i\) (\(1 \le a_i \le m\));

Các số trong tệp cách nhau bởi dấu cách.

Output

• In ra 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

3 3
1 2 3

1

Scoring

• Subtask \(1\) (\(2{,}0\) điểm): \(1 \le n \le 100, 1 \le m \le 10^3\)
• Subtask \(2\) (\(1{,}5\) điểm): \(100 \le n \le 5 \cdot 10^3, 1 \le m \le 10^9\)
• Subtask \(3\) (\(1{,}5\) điểm): Không ràng buộc gì thêm