#include <bits/stdc++.h>
using namespace std;
const int N = 2 * 200000 + 7;
const int INF = (int) 1e9 + 7;
int n;
int r;
int my_rank;
int init_ord[N];
int ord[N];
int winner[N];
int loser[N];
bool wannap;
int thesol[N];
int rep(int x) {
x %= n;
if (x < 0) x += n;
return x;
}
enum TYPE {SMALL, EQUAL, BIG};
int cnt_big[N];
int cnt_equal[N];
TYPE type[N];
int low, high;
pair<int, TYPE> guys[2 * N];
TYPE gettype(int val) {
if (val == my_rank) {
return EQUAL;
}
if (val < my_rank) {
return SMALL;
}
if (val > my_rank) {
return BIG;
}
assert(0);
}
struct MySet {
map<TYPE, int> f;
void ins(TYPE val) {
f[val]++;
}
TYPE getsm() {
for (auto &it : f) {
if (it.second) {
it.second--;
return it.first;
}
}
assert(0);
}
void clr() {
f.clear();
}
};
int get_smart(int x) {
if (my_rank == 0) {
return 0;
}
if (my_rank <= n) {
int pos = 2 * x;
ord[pos] = my_rank;
for (int i = 0; i < pos; i++) {
ord[i] = init_ord[i];
}
for (int i = pos + 1; i < 2 * n; i++) {
ord[i] = init_ord[i - 1];
}
low = 1;
high = 0;
for (int i = 0; i < 2 * n; i++) {
guys[++high] = {i / 2, gettype(ord[i])};
}
TYPE ant = max(gettype(ord[0]), gettype(ord[1]));
MySet myset;
vector<TYPE> mxs;
for (int iter = 1; iter <= r; iter++) {
while (low <= high && guys[low].first < iter) myset.ins(guys[low++].second);
TYPE smallest = myset.getsm();
if (iter == 1) {
myset.clr();
}
int nw = iter - 1 + n;
TYPE mx = max(smallest, ant);
TYPE mn = min(smallest, ant);
mxs.push_back(mx);
ant = mn;
guys[++high] = {nw, mx};
}
int last_seen = -1, transfering = 0;
for (int i = 0; i < r; i++) {
if (mxs[i] == EQUAL) {
last_seen = i;
transfering++;
}
}
int thepos = n - (r - 1 - last_seen) - 1;
return thepos - n * transfering;
}
int pos = 2 * x;
ord[pos] = my_rank;
for (int i = 0; i < pos; i++) {
ord[i] = init_ord[i];
}
for (int i = pos + 1; i < 2 * n; i++) {
ord[i] = init_ord[i - 1];
}
for (int i = 0; i < 2 * n; i++) {
if (ord[i] == my_rank) {
type[i] = EQUAL;
}
if (ord[i] > my_rank) {
type[i] = BIG;
}
if (ord[i] < my_rank) {
type[i] = SMALL;
}
}
for (int i = 0; i < n; i++) {
cnt_big[i] = (type[2 * i] == BIG) + (type[2 * i + 1] == BIG);
cnt_equal[i] = (type[2 * i] == EQUAL) + (type[2 * i + 1] == EQUAL);
}
int big_in_hand = 0, equal_in_hand = 0, transfering = 0;
function<void()> handle0 = [&] () {
/// if EQUAL vs BIG => EQUAL remains, BIG goes
int the_sum = cnt_big[0] + cnt_equal[0];
big_in_hand += cnt_big[0];
equal_in_hand += cnt_equal[0];
cnt_big[0] = cnt_equal[0] = 0;
if (the_sum != 2) {
/// there is a small one and it pushes them away
transfering += (equal_in_hand);
return;
}
if (equal_in_hand) {
cnt_equal[0] = 1;
equal_in_hand = 0;
} else {
if (big_in_hand) {
cnt_big[0] = 1;
big_in_hand--;
}
}
transfering += (equal_in_hand);
};
function<void(int)> handlenot0 = [&] (int i) {
/// if EQUAL vs BIG => BIG remains, EQUAL goes
big_in_hand += cnt_big[i];
equal_in_hand += cnt_equal[i];
cnt_big[i] = cnt_equal[i] = 0;
if (big_in_hand) {
cnt_big[i] = 1;
big_in_hand--;
} else {
if (equal_in_hand) {
cnt_equal[i] = 1;
equal_in_hand = 0;
}
}
};
handle0();
for (int i = n - 1; i >= 1; i--) handlenot0(i);
handle0();
for (int i = n - 1; i >= 1; i--) handlenot0(i);
int thepos = -1;
for (int i = 0; i < n; i++) {
if (cnt_equal[i]) {
thepos = i;
}
}
assert(thepos != -1);
return thepos - n * transfering;
}
int get(int x) {
if (thesol[x] != INF) {
return thesol[x];
}
thesol[x] = get_smart(x);
return thesol[x];
}
int mn = (int) 1e9;
int best = -1;
void upd(int i) {
int x = get(i);
int y = rep(x);
if (y < mn) {
mn = y;
best = i;
} else {
if (y == mn) {
best = max(best, i);
}
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input", "r", stdin);
for (int i = 0; i < N; i++) {
thesol[i] = INF;
}
wannap = 0;
cin >> n >> r;
r = 2 * n + r % n;
cin >> my_rank;
my_rank--;
for (int i = 0; i < 2 * n - 1; i++) {
cin >> init_ord[i];
init_ord[i]--;
}
upd(0);
upd(n - 1);
{
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
upd(mid);
if (get(mid) == get(0)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
int L = get(0), R = get(n - 1);
for (int j = L; j <= R; j++) {
if (j % n) {
continue;
}
int low = 0, high = n - 1, the_value = INF;
while (low <= high) {
int mid = (low + high) / 2;
upd(mid);
if (get(mid) >= j) {
high = mid - 1;
the_value = mid;
} else {
low = mid + 1;
}
}
low = the_value;
high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
upd(mid);
if (get(mid) == get(the_value)) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
cout << best + 1 << "\n";
return 0;
}
