solution-code3586

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#include <climits>
6
#include <cmath>
7
using namespace std;
8
int n,m,a[100005],b[100005][20],sum[100005];
9
inline void ST(void)
10
{
11
  int i,j;
12
  for(j=1;(1<<j)<=n;++j)
13
  {
14
    for(i=1;i+(1<<j)-1<=n;++i)
15
    {
16
      b[i][j]=max(b[i][j-1],b[i+(1<<(j-1))][j-1]);
17
    }
18
  }
19
  return;
20
}
21
inline int ask(int L,int R)
22
{
23
  if(L>R)return 0;
24
  int x=int((log(R-L+1))/log(2));
25
  return max(b[L][x],b[R-(1<<x)+1][x]);
26
}
27
int main(void)
28
{
29
  int i,pos,L,R;
30
  scanf("%d%d",&n,&m);pos=n;
31
  for(i=1;i<=n;++i)
32
  {
33
    scanf("%d",&a[i]);
34
    if(a[i]==a[i-1])b[i][0]=b[i-1][0]+1;
35
    else b[i][0]=1;
36
  }
37
  for(i=n;i>=1;--i)
38
  {
39
    if(a[i]==a[i+1])sum[i]=b[pos][0];
40
    else pos=i,sum[i]=b[pos][0];
41
  }
42
  ST();
43
  for(i=1;i<=m;++i)
44
  {
45
    scanf("%d%d",&L,&R);
46
    printf("%d\n",min(R-L+1,max(max(sum[L]-b[L][0]+1,b[R][0]),ask(L+sum[L]-b[L][0]+1,R-b[R][0]))));
47
  }
48
  return 0;
49
}