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ị ~\{1, 2, 2, 4\}~ với 6 hộp quà còn lại ~\{3, 2, 4, 5, 2, 3\}~ tạo thành 4 giỏ quà được ghép là ~\{(1, 2), (2, 3), (2, 3), (4, 5)\}~ 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_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

Số ~K~ lớn nhất tìm được, nếu không có nghiệm thì ghi ra -1.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

5 6
5 4 2 1 2

Sample Output 2

-1

Sample Input 3

3 3
1 2 3

Sample Output 3

1

Subtasks