#include <bits/stdc++.h>
using namespace std;
struct SegTree {
int n;
vector<int> mn, lazy;
SegTree() {}
SegTree(const vector<int>& a) { init(a); }
void init(const vector<int>& a) {
n = (int)a.size() - 1; // 1-based
mn.assign(4 * n + 5, 0);
lazy.assign(4 * n + 5, 0);
build(1, 1, n, a);
}
void build(int node, int l, int r, const vector<int>& a) {
if (l == r) {
mn[node] = a[l];
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid, a);
build(node << 1 | 1, mid + 1, r, a);
mn[node] = min(mn[node << 1], mn[node << 1 | 1]);
}
void apply(int node, int val) {
mn[node] += val;
lazy[node] += val;
}
void push(int node) {
if (lazy[node] != 0) {
apply(node << 1, lazy[node]);
apply(node << 1 | 1, lazy[node]);
lazy[node] = 0;
}
}
void range_add(int ql, int qr, int val) {
if (ql > qr) return;
range_add(1, 1, n, ql, qr, val);
}
void range_add(int node, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
apply(node, val);
return;
}
push(node);
int mid = (l + r) >> 1;
if (ql <= mid) range_add(node << 1, l, mid, ql, qr, val);
if (qr > mid) range_add(node << 1 | 1, mid + 1, r, ql, qr, val);
mn[node] = min(mn[node << 1], mn[node << 1 | 1]);
}
int range_min(int ql, int qr) {
if (ql > qr) return INT_MAX;
return range_min(1, 1, n, ql, qr);
}
int range_min(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return mn[node];
push(node);
int mid = (l + r) >> 1;
int ans = INT_MAX;
if (ql <= mid) ans = min(ans, range_min(node << 1, l, mid, ql, qr));
if (qr > mid) ans = min(ans, range_min(node << 1 | 1, mid + 1, r, ql, qr));
return ans;
}
int point_get(int pos) {
return point_get(1, 1, n, pos);
}
int point_get(int node, int l, int r, int pos) {
if (l == r) return mn[node];
push(node);
int mid = (l + r) >> 1;
if (pos <= mid) return point_get(node << 1, l, mid, pos);
return point_get(node << 1 | 1, mid + 1, r, pos);
}
// k-th record low in [ql, qr], scanning left->right, initial threshold = cur
int kth_record_low(int ql, int qr, int cur, int k) {
return kth_record_low(1, 1, n, ql, qr, cur, k).first;
}
pair<int, pair<int,int>> kth_record_low(int node, int l, int r,
int ql, int qr, int cur, int k) {
if (r < ql || l > qr) return {-1, {cur, k}};
if (ql <= l && r <= qr) {
int cnt = max(0, cur - mn[node]);
if (cnt < k) {
return {-1, {min(cur, mn[node]), k - cnt}};
}
if (l == r) {
return {l, {cur, k}};
}
}
push(node);
int mid = (l + r) >> 1;
auto left = kth_record_low(node << 1, l, mid, ql, qr, cur, k);
if (left.first != -1) return left;
return kth_record_low(node << 1 | 1, mid + 1, r, ql, qr,
left.second.first, left.second.second);
}
};
struct ParkingQuery {
int L;
int total;
int constant; // total - L
SegTree st;
ParkingQuery() {}
ParkingQuery(const vector<int>& cnt) { init(cnt); }
void init(const vector<int>& cnt) {
L = (int)cnt.size() - 1; // 1-based
total = 0;
for (int i = 1; i <= L; ++i) total += cnt[i];
constant = total - L;
vector<int> D(2 * L + 1, 0); // 1..2L
int pref = 0;
for (int i = 1; i <= 2 * L; ++i) {
pref += cnt[(i - 1) % L + 1];
D[i] = pref - i;
}
st.init(D);
}
// cnt[pos] += delta
void add_slot(int pos, int delta) {
if (delta == 0) return;
total += delta;
constant += delta;
st.range_add(pos, 2 * L, delta);
st.range_add(pos + L, 2 * L, delta);
}
// first empty slot when scanning cyclically from s
int first_empty(int s) {
int threshold = (s == 1 ? 0 : st.point_get(s - 1));
int minRange = min(threshold, st.range_min(s, s + L - 1));
int k = threshold + constant - minRange + 1;
int pos = st.kth_record_low(s, s + L - 1, threshold, k);
if (pos > L) pos -= L;
return pos;
}
};
static inline int nxt_cyclic(int x, int N) {
return (x == N ? 1 : x + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
long long R;
cin >> N >> R;
int myRank;
cin >> myRank;
vector<int> other(2 * N); // 1..2N-1
for (int i = 1; i <= 2 * N - 1; ++i) cin >> other[i];
if (N == 1) {
cout << 1 << '\n';
return 0;
}
vector<int> strong(2 * N, 0), weak(2 * N, 0);
int K = 0; // stronger opponents
for (int i = 1; i <= 2 * N - 1; ++i) {
strong[i] = (other[i] < myRank ? 1 : 0);
weak[i] = 1 - strong[i];
K += strong[i];
}
int bestFinal = INT_MAX;
int bestStart = 1;
auto relax = [&](int startTarget, int finalTarget) {
if (finalTarget < bestFinal || (finalTarget == bestFinal && startTarget > bestStart)) {
bestFinal = finalTarget;
bestStart = startTarget;
}
};
if (K == 0) {
// I beat everyone, so I always end at target 1.
// Tie-breaker => largest starting target.
cout << N << '\n';
return 0;
}
if (K <= N) {
// Sparse regime on stronger archers.
vector<int> B(N + 1, 0); // stronger-opponent counts on targets for current t
B[1] = strong[1];
for (int i = 2; i <= N; ++i) {
B[i] = strong[2 * i - 2] + strong[2 * i - 1];
}
set<int> positive;
for (int i = 1; i <= N; ++i) {
if (B[i] > 0) positive.insert(i);
}
// Parking counts of existing stronger archers after removing leftmost champion
vector<int> cnt(N + 1, 0);
for (int i = 1; i <= N; ++i) cnt[i] = B[i];
int p = *positive.begin();
if (p == 1) {
cnt[1] -= 1;
} else {
cnt[p] -= B[p];
cnt[nxt_cyclic(p, N)] += B[p] - 1;
}
ParkingQuery pq(cnt);
int rot = (int)(R % N);
auto changeB = [&](int idx, int delta) {
if (delta == 0) return;
if (B[idx] > 0) positive.erase(idx);
B[idx] += delta;
if (B[idx] > 0) positive.insert(idx);
};
for (int t = 1; t <= N; ++t) {
int firstStrong = *positive.begin();
int prefSlot;
if (t < firstStrong) {
prefSlot = firstStrong;
} else if (B[t] == 0) {
prefSlot = t;
} else if (t == 1) {
prefSlot = 1;
} else {
prefSlot = nxt_cyclic(t, N);
}
int slot = pq.first_empty(prefSlot);
int finalTarget = ((slot - rot - 1) % N + N) % N + 1;
relax(t, finalTarget);
if (t == N) break;
// Remove old champion correction
int oldP = firstStrong;
int oldBP = B[oldP];
if (oldP == 1) {
pq.add_slot(1, +1);
} else {
pq.add_slot(oldP, +oldBP);
pq.add_slot(nxt_cyclic(oldP, N), -(oldBP - 1));
}
// Boundary moves from t to t+1
int delta = strong[2 * t];
changeB(t, +delta);
pq.add_slot(t, +delta);
changeB(t + 1, -delta);
pq.add_slot(t + 1, -delta);
// Apply new champion correction
int newP = *positive.begin();
int newBP = B[newP];
if (newP == 1) {
pq.add_slot(1, -1);
} else {
pq.add_slot(newP, -newBP);
pq.add_slot(nxt_cyclic(newP, N), +(newBP - 1));
}
}
} else {
// Dense regime on stronger archers == sparse regime on weaker archers.
vector<int> W(N + 1, 0); // weaker-opponent counts on targets for current t
W[1] = weak[1];
for (int i = 2; i <= N; ++i) {
W[i] = weak[2 * i - 2] + weak[2 * i - 1];
}
int L = N - 1;
vector<int> cnt(L + 1, 0); // slot 1 <-> target N, slot 2 <-> target N-1, ...
cnt[1] = W[1] + W[N];
for (int s = 2; s <= L; ++s) {
cnt[s] = W[N - s + 1];
}
ParkingQuery pq(cnt);
auto dense_slot_of_target = [&](int target) {
if (target == 1 || target == N) return 1;
return N - target + 1;
};
for (int t = 1; t <= N; ++t) {
int prefSlot = (t == 1 ? 1 : N - t + 1);
int slot = pq.first_empty(prefSlot);
int finalTarget = N - slot + 1;
relax(t, finalTarget);
if (t == N) break;
int delta = weak[2 * t];
W[t] += delta;
pq.add_slot(dense_slot_of_target(t), +delta);
W[t + 1] -= delta;
pq.add_slot(dense_slot_of_target(t + 1), -delta);
}
}
cout << bestStart << '\n';
return 0;
}
