#include "lottery.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 2e5 + 5;
const int LIM = 2e9 + 2;
template<class T>void minimize(T& a, T b){
if(a > b){
a = b;
}
}
int n, q, lgv[lim], spt[19][lim];
int get_min_sum(int l, int r){
int k = lgv[r - l + 1];
return min(spt[k][l], spt[k][r - (1 << k) + 1]);
}
vector<int>x, y;
struct PersistentSegmentTree{
struct Node{
int cnt, lc, rc;
ll sum;
Node(){
lc = rc = -1;
cnt = sum = 0;
}
};
vector<Node>st;
void update(int id, int l, int r, const int p){
st[id].sum += p;
st[id].cnt++;
if(l == r){
return;
}
int m = l + ((r - l) >> 1);
if(st[id].lc == -1){
st[id].lc = st.size();
st.push_back(Node());
}
else{
st.push_back(st[st[id].lc]);
st[id].lc = int(st.size()) - 1;
}
if(st[id].rc == -1){
st[id].rc = st.size();
st.push_back(Node());
}
else{
st.push_back(st[st[id].rc]);
st[id].rc = int(st.size()) - 1;
}
if(m < p){
update(st[id].rc, m + 1, r, p);
}
else{
update(st[id].lc, l, m, p);
}
}
void init(const vector<int>& value){
st.assign(n + 1, Node());
for(int i = 1; i <= n; i++){
st[i] = st[i - 1];
update(i, 0, LIM, value[i]);
}
for(int i = 0; i < st.size(); i++){
if(st[i].lc == -1){
st[i].lc = st.size();
}
if(st[i].rc == -1){
st[i].rc = st.size();
}
}
st.push_back(Node());
st.back().lc = st.back().rc = int(st.size()) - 1;
}
int query(int lq, int rq, int max_cnt){
int idl = lq - 1, idr = rq, l = 0, r = LIM, small_cnt = 0, ans = 0, N = idr - idl;
ll small_sum = 0;
while(l < r){
int m = l + ((r - l) >> 1);
if(m > max_cnt){
idl = st[idl].lc;
idr = st[idr].lc;
r = m;
}
else{
ll new_sum = st[st[idr].lc].sum - st[st[idl].lc].sum + small_sum;
int new_cnt = st[st[idr].lc].cnt - st[st[idl].lc].cnt + small_cnt;
if(new_sum + ll((N >> 1) - new_cnt) * m > -1){
l = (ans = m) + 1;
idl = st[idl].rc;
idr = st[idr].rc;
small_sum = new_sum;
small_cnt = new_cnt;
}
else{
r = m;
idl = st[idl].lc;
idr = st[idr].lc;
}
}
}
return ans;
}
};
PersistentSegmentTree stx, sty;
void init(int _n, int _q, vector<int>_x, vector<int>_y){
n = _n;
q = _q;
swap(x, _x);
swap(y, _y);
x.insert(x.begin(), 0);
y.insert(y.begin(), 0);
stx.init(x);
sty.init(y);
lgv[0] = -1;
for(int i = 1; i <= n; i++){
spt[0][i] = x[i] + y[i];
lgv[i] = lgv[i >> 1] + 1;
}
for(int i = 1; i < 18; i++){
for(int j = 1; j + (1 << i) - 1 <= n; j++){
spt[i][j] = min(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
}
}
}
int max_prize(int l, int r){
int min_cnt = get_min_sum(++l, ++r);
return min(stx.query(l, r, min_cnt), sty.query(l, r, min_cnt));
}
