#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
const int inf_32 = 0x3f3f3f3f;
struct FenwickTree {
vector <int> node;
int N;
FenwickTree(int N): N(N), node(N) {
for (int i = 0; i < N; ++i) {
node[i] = (i + 1) & -(i + 1);
}
}
int find_value_by_order(int s) {
int p = -1;
for (int i = __lg(N); i >= 0; --i) {
if (p + (1 << i) >= N) continue;
if (node[p + (1 << i)] < s) {
p += 1 << i;
s -= node[p];
}
}
p += 1;
return p;
}
void update(int u, int v) {
for (; u < N; u |= u + 1) {
node[u] += v;
}
}
int ask(int u) {
int ans = 0;
for (; u >= 0; u = (u & (u + 1)) - 1) {
ans += node[u];
}
return ans;
}
int ask_range(int l, int r) {
return ask(r) - ask(l - 1);
}
void reset() {
node.assign(N, 0);
}
};
int GetBestPosition(int N, int M, int R, int *K, int *S, int *E) {
vector <int> value(N);
value[0] = R;
for (int i = 0; i + 1 < N; ++i) {
value[i + 1] = K[i];
}
vector <int> temp_ID(N);
iota(temp_ID.begin(), temp_ID.end(), 0);
vector <vector <int>> graph(N + M);
FenwickTree tree(N + M);
for (int i = 0; i < M; ++i) {
S[i] += 1; E[i] += 1;
vector <int> vertex_id(E[i] - S[i] + 1);
for (int j = 0; j < (int) vertex_id.size(); ++j) {
int pos = tree.find_value_by_order(j + S[i]);
vertex_id[j] = temp_ID[pos];
graph[i + N].push_back(vertex_id[j]);
}
temp_ID[tree.find_value_by_order(S[i])] = i + N;
for (int j = (int) vertex_id.size() - 1; j; --j) {
tree.update(tree.find_value_by_order(j + S[i]), -1);
}
}
const int root = N + M - 1;
vector <int> time_in(N + M), time_out(N + M), depth(N + M);
vector <vector <int>> anc(__lg(N + M) + 1, vector <int> (N + M));
int timeDFS = -1;
auto DFS = [&] (auto DFS, int u) -> void {
time_in[u] = ++timeDFS;
for (int v : graph[u]) {
depth[v] = depth[u] + 1;
anc[0][v] = u;
DFS(DFS, v);
}
time_out[u] = timeDFS;
};
DFS(DFS, root);
tree.reset();
vector <int> state(N);
for (int i = 0; i < N; ++i) {
state[i] = value[0] < value[i];
tree.update(time_in[i], +state[i]);
}
for (int i = 1; i <= __lg(N + M); ++i) {
for (int u = 0; u < N + M; ++u) {
anc[i][u] = anc[i - 1][anc[i - 1][u]];
}
}
pair <int, int> optimal_ans{-inf_32, -1};
for (int u = 0; u < N; ++u) {
int x = u;
for (int i = __lg(depth[u]); i >= 0; --i) {
if (depth[x] < (1 << i)) continue;
int nxt_x = anc[i][x];
if (tree.ask_range(time_in[nxt_x], time_out[nxt_x]) == 0) {
x = nxt_x;
}
}
optimal_ans = max(optimal_ans, make_pair(depth[u] - depth[x], -u));
if (u + 1 < N) {
tree.update(time_in[u], -state[u]);
tree.update(time_in[u + 1], -state[u + 1]);
swap(state[u], state[u + 1]);
tree.update(time_in[u], +state[u]);
tree.update(time_in[u + 1], +state[u + 1]);
}
}
optimal_ans.second = -optimal_ans.second;
return optimal_ans.second;
}
