#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=5e3+55;
pair < int , int > b[N];
int tree[N*4];
int lazy[N*4];
bool vis[N];
int a[N];
void build(int l , int r , int node)
{
if(r==l)
{
tree[node]=l;
return ;
}
int mid=(l+r)/2;
build(l,mid,node*2);
build(mid+1,r,node*2+1);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
void propagate(int l , int r , int node )
{
tree[node]-=lazy[node];
if(l!=r)
{
lazy[node*2]=lazy[node];
lazy[node*2+1]=lazy[node];
}
lazy[node]=0;
}
int query(int l , int r , int node , int x)
{
if(lazy[node])
propagate(l,r,node);
if(tree[node]==x&&l==r)
return l;
int mid=(l+r)/2;
if(tree[node*2]>=x)
return query(l,mid,node*2,x);
else
return query(mid+1,r,node*2+1,x);
}
void update(int l , int r , int node , int x , int y , int val)
{
if(lazy[node])
propagate(l,r,node);
if(x<r||l>y)
return ;
if(x<=l&&y>=r)
{
lazy[node]+=val;
propagate(l,r,node);
return ;
}
int mid=(l+r)/2;
update(l,mid,node*2,x,y,val);
update(mid+1,r,node*2+1,x,y,val);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
int GetBestPosition(int n, int m, int R, int *K, int *S, int *E) {
int s,e;
int best=0;
int cur=0;
build(0,n-1,1);
for(int i=0;i<n;i++)
{
cur=0;
for(int j=0;j<n;j++)
{
if(j==i)
{
a[j]=R;
continue ;
}
a[j]=K[cur];
cur++;
}
cur=0;
int x,temp;
for(int j=0;j<m;j++)
{
s=query(0,n-1,1,S[j]);
e=query(0,n-1,1,E[j]);
for(int k=s;k<=e;k++)
{
if(a[k]>temp)
{
temp=a[k];
x=k;
}
}
update(0,n-1,1,e+1,n-1,e-s);
update(0,n-1,1,s,x-1,-1e5);
update(0,n-1,1,x+1,e,-1e5);
if(temp==R)
cur++;
}
best=max(best,cur);
}
return best;
}
