#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
int N;
int Q;
int X[200100];
int Y[200100];
void init(int N, int Q, std::vector<int> X, std::vector<int> Y) {
::N = N;
::Q = Q;
for(int i = 0; i < N; i++) ::X[i] = X[i];
for(int i = 0; i < N; i++) ::Y[i] = Y[i];
}
int max_prize(int l, int r) {
if(r - l + 1 > 100) return 1;
vector<pair<int,pair<int,int>>> vr;
for(int i = l; i <= r; i++){
vr.push_back({min(Y[i],X[i]),make_pair(X[i],Y[i])});
}
sort(vr.begin(),vr.end());
int cont = 0;
while(true){
int r = 0;
int b = 0;
bool can = true;
for(int i = 0; i < vr.size(); i++){
if(b == vr.size()/2){
if(vr[i].second.first == 0) can = false;
else{
vr[i].second.first--;
vr[i].first = min(vr[i].second.first,vr[i].second.second);
}
}
else if(r == vr.size()/2){
if(vr[i].second.second == 0) can = false;
else{
vr[i].second.second--;
vr[i].first = min(vr[i].second.first,vr[i].second.second);
}
}
else{
if(max(vr[i].second.first,vr[i].second.second) == 0){
can = false;
break;
}
if(vr[i].second.first >= vr[i].second.second){
vr[i].second.first--;
vr[i].first = min(vr[i].second.first,vr[i].second.second);
r++;
}
else{
vr[i].second.second--;
vr[i].first = min(vr[i].second.first,vr[i].second.second);
b++;
}
}
}
if(!can) break;
sort(vr.begin(),vr.end());
//for(pair<int,pair<int,int>> iii : vr) printf("%d %d %d\n",iii.first,iii.second.first,iii.second.second);
//printf("\n");
cont++;
}
return cont;
}
/*
int main(){
init(5, 3, {2, 1, 3, 1, 0}, {1, 1, 0, 2, 0});
printf("%d ",max_prize(0, 3));
}*/
