Một giải đấu bắn cung được tổ chức theo các quy tắc sau. Có \(N\) bia được xếp thành một hàng và đánh số từ \(1\) đến \(N\) theo vị trí trên hàng: bia ngoài cùng bên trái mang số \(1\), còn bia ngoài cùng bên phải mang số \(N\). Có \(2N\) cung thủ tham gia. Tại mọi thời điểm trong giải đấu, mỗi bia có hai cung thủ. Mỗi vòng đấu diễn ra như sau: hai cung thủ ở mỗi bia thi đấu với nhau để xác định người thắng và người thua, sau đó tất cả cung thủ được sắp xếp lại theo quy tắc:

• Những người thắng ở các bia từ \(2\) đến \(N\) chuyển sang bia bên trái, tức lần lượt là các bia từ \(1\) đến \(N-1\).
• Những người thua ở các bia từ \(2\) đến \(N\), cùng với người thắng ở bia \(1\), vẫn ở nguyên bia của mình.
• Người thua ở bia \(1\) chuyển sang bia \(N\).

Giải đấu kéo dài \(R\) vòng, với số vòng ít nhất bằng số cung thủ, tức \(R \ge 2N\).

Bạn là cung thủ duy nhất đến giải đấu đúng giờ. Tất cả \(2N-1\) cung thủ còn lại đều đã đến sớm và đang đứng thành một hàng. Bây giờ bạn phải chen vào một vị trí nào đó trong hàng của họ. Bạn biết rằng sau khi bạn vào hàng, hai cung thủ ngoài cùng bên trái sẽ bắt đầu giải đấu ở bia \(1\), hai người tiếp theo ở bia \(2\), và cứ như vậy cho đến hai cung thủ ngoài cùng bên phải bắt đầu ở bia \(N\).

Cả \(2N\) cung thủ trong giải đấu, kể cả bạn, đều được xếp hạng theo kỹ năng; số thứ hạng càng nhỏ thì kỹ năng càng tốt. Không có hai cung thủ nào cùng thứ hạng. Khi hai cung thủ thi đấu với nhau, người có số thứ hạng nhỏ hơn luôn thắng.

Biết kỹ năng của từng đối thủ, bạn muốn chọn vị trí chen vào hàng sao cho khi giải đấu kết thúc, bạn ở một bia có số nhỏ nhất có thể. Nếu có nhiều cách đạt được điều đó, bạn muốn chọn cách bắt đầu ở bia có số lớn nhất có thể.

Nhiệm vụ

Cho thứ hạng của tất cả cung thủ, bao gồm cả bạn, cùng thứ tự các đối thủ đang đứng trong hàng, hãy viết chương trình xác định bia mà bạn nên bắt đầu giải đấu để đạt được các mục tiêu trên.

Dữ liệu vào

Chương trình đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(N\) và \(R\), cách nhau bởi một dấu cách.
• \(2N\) dòng tiếp theo cho biết thứ hạng của các cung thủ. Dòng đầu tiên trong số này chứa thứ hạng của bạn. Các dòng còn lại chứa thứ hạng của các cung thủ khác, mỗi người một dòng, theo thứ tự họ đang đứng từ trái sang phải. Mỗi dòng chứa một số nguyên từ \(1\) đến \(2N\), trong đó hạng \(1\) là tốt nhất và hạng \(2N\) là kém nhất. Không có hai cung thủ nào cùng thứ hạng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên từ \(1\) đến \(N\): số của bia mà bạn sẽ bắt đầu giải đấu.

Ràng buộc

• \(1 \le N \le 200\,000\): số bia, cũng bằng một nửa số cung thủ.
• \(2N \le R \le 1\,000\,000\,000\): số vòng đấu.
• \(1 \le S_k \le 2N\): thứ hạng của cung thủ \(k\).

Phân nhóm

Bài có tổng cộng \(100\) điểm. Trong một số test có tổng cộng \(60\) điểm, \(N\) không vượt quá \(5000\). Trong số các test này, một số test có tổng cộng \(20\) điểm thỏa mãn \(N\) không vượt quá \(200\).

Ví dụ

4 8
7
4
2
6
5
8
1
3

3

4 9
2
1
5
8
3
4
7
6

2

Nguồn

IOI 2009.