#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e5 + 10;
vector <int> save[N];
struct fen{
vector <ll> f;
int N;
void ass(int n) {
N = n;
f.assign(N + 1, 0);
}
void upd(int i, ll x) {
for (; i; i -= i & (-i))
f[i] += x;
}
ll get(int i) {
ll s = 0;
for (; i <= N; i += i & (-i))
s += f[i];
return s;
}
};
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
int n = N;
int c = C;
int r = R;
for (int i = 0; i < c; i++) {
S[i]++;
E[i] += 2;
}
set <int> pos;
for (int i = 1; i < n; i++) {
if (K[i - 1] > r) {
pos.insert(i);
}
}
pos.insert(n + 1);
for (int i = 0; i < c; i++) {
auto it = pos.lower_bound(S[i]);
E[i] = min(E[i], *it);
save[S[i]].pb(E[i]);
}
fen f1, f2;
f1.ass(n + 10);
f2.ass(n + 10);
ll ans = 0, p = 0;
for (ll i = 1; i <= n; i++) {
for (auto x : save[i]) {
f1.upd(x, 1);
f2.upd(x, x);
}
ll v = f2.get(i) - f1.get(i) * i;
if (ans < v) {
ans = v;
p = i - 1;
}
}
for (int i = 0; i < N; i++)
save[i].clear();
return p;
}
