Trong đám cưới với Beatrice d'Este năm \(1491\), Công tước thành Milan Lodovico Sforza nhờ Leonardo tổ chức lễ hội, trong đó có một giải đấu thương lớn kéo dài suốt ba ngày. Thế nhưng hiệp sĩ được hâm mộ nhất lại đến muộn…

Giải đấu

Ban đầu, \(N\) hiệp sĩ đứng thành một hàng, được đánh số vị trí từ \(0\) đến \(N-1\) theo thứ tự trong hàng. Trọng tài tổ chức một vòng đấu bằng cách gọi hai vị trí \(S,E\), với \(0 \le S<E \le N-1\). Tất cả hiệp sĩ từ vị trí \(S\) đến \(E\), kể cả hai đầu, cùng tranh tài. Người thắng tiếp tục thi đấu và trở về vị trí của mình; những người thua bị loại và rời hàng. Các hiệp sĩ còn lại dồn về đầu hàng, giữ nguyên thứ tự tương đối, để các vị trí mới liên tiếp từ \(0\) đến \(N-(E-S)-1\). Trọng tài tiếp tục gọi các vòng đấu theo cách này cho đến khi chỉ còn một hiệp sĩ.

Leonardo biết sức mạnh của các hiệp sĩ đôi một khác nhau, biểu diễn bằng thứ hạng từ \(0\) (yếu nhất) đến \(N-1\) (mạnh nhất). Ông cũng biết chính xác các cặp vị trí mà trọng tài sẽ gọi trong \(C\) vòng đấu: dù sao thì ông cũng là Leonardo! Trong mỗi vòng, hiệp sĩ có thứ hạng cao nhất chắc chắn thắng.

Có \(N-1\) hiệp sĩ đã xếp hàng; chỉ còn thiếu hiệp sĩ được hâm mộ nhất, có thứ hạng \(R\). Để tăng sức hấp dẫn của giải đấu, Leonardo muốn chọn vị trí chèn hiệp sĩ này vào hàng sao cho số vòng anh ta thắng là lớn nhất. Chỉ tính những vòng mà anh ta tham gia và thắng; những vòng anh ta không tham gia không được tính.

Yêu cầu và giao diện

Cài đặt GetBestPosition(N, C, R, K, S, E) với các tham số:

• \(N\): tổng số hiệp sĩ.
• \(C\): số vòng đấu, \(1 \le C \le N-1\).
• \(R\): thứ hạng của hiệp sĩ đến muộn. Thứ hạng của tất cả hiệp sĩ, kể cả người đến muộn, đôi một khác nhau và thuộc \(0,\ldots,N-1\). \(R\) được cho trực tiếp dù có thể suy ra từ các thứ hạng còn lại.
• \(K\): mảng \(N-1\) số nguyên, chứa thứ hạng của các hiệp sĩ đã có mặt theo thứ tự trong hàng ban đầu.
• \(S,E\): hai mảng có \(C\) phần tử. Với \(0 \le i \le C-1\), vòng thứ \(i+1\) gồm mọi hiệp sĩ từ vị trí \(S[i]\) đến \(E[i]\) trong hàng hiện tại, kể cả hai đầu. Bảo đảm \(S[i]<E[i]\).

Các cặp vị trí đều hợp lệ: \(E[i]\) nhỏ hơn số hiệp sĩ còn lại trước vòng thứ \(i+1\), và sau tất cả \(C\) vòng chỉ còn đúng một hiệp sĩ.

Hàm phải trả về vị trí tốt nhất \(P\), với \(0 \le P \le N-1\), để số vòng hiệp sĩ đến muộn thắng là lớn nhất. Nếu có nhiều vị trí cùng tối ưu, trả về vị trí nhỏ nhất. \(P\) là chỉ số bắt đầu từ \(0\) của hiệp sĩ đến muộn trong hàng sau khi chèn, hay chính là số hiệp sĩ đứng trước anh ta. \(P=0\) nghĩa là đầu hàng; \(P=N-1\) nghĩa là cuối hàng.

Chi tiết cài đặt

Nộp đúng một tệp tournament.c, tournament.cpp hoặc tournament.pas, cài đặt chương trình con với chữ ký sau.

C/C++

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E);

Pascal

function GetBestPosition(N, C, R : LongInt; var K, S, E : array of LongInt) : LongInt;

Chương trình con phải hoạt động như đã mô tả. Bạn có thể cài đặt thêm các chương trình con dùng nội bộ. Bài nộp không được giao tiếp dưới bất kỳ hình thức nào với đầu vào/đầu ra chuẩn hoặc với bất kỳ tệp nào khác.

Dữ liệu vào

Trình chấm mẫu trong môi trường thi nhận dữ liệu như sau:

• Dòng \(1\): N C R.
• Các dòng \(2,\ldots,N\): mỗi dòng chứa một giá trị \(K[i]\), theo thứ tự \(i=0,\ldots,N-2\).
• Các dòng \(N+1,\ldots,N+C\): mỗi dòng chứa S[i] E[i], theo thứ tự \(i=0,\ldots,C-1\).

Dữ liệu ra

Hàm GetBestPosition trả về vị trí \(P\) nhỏ nhất trong các vị trí cho số vòng thắng lớn nhất.

Ràng buộc

• \(1 \le C \le N-1\).
• \(R\) và các phần tử của \(K\) là các thứ hạng đôi một khác nhau từ \(0\) đến \(N-1\).
• Với mỗi vòng \(i\), \(0 \le S[i]<E[i]\) và \(E[i]\) nhỏ hơn số hiệp sĩ hiện còn trong hàng. Sau \(C\) vòng còn đúng một hiệp sĩ.
• Giới hạn thời gian: \(1\) giây.
• Giới hạn bộ nhớ: \(256\) MiB.

Phân nhóm

Ví dụ

5 3 3
1
0
2
4
1 3
0 1
0 1

1