uva 11235 - Frequent values

//============================================================================
// Name        : 11235.cpp
// Author      : Mr Tu
// Version     :
// Copyright   : Your copyright notice
// Description : Uva 11235 - Frequent values in C++, Ansi-style
// Problem link
// Algorithm: Data structure - Segment tree
//============================================================================

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <fstream>
using namespace std;
const int maxn = 100010;
//-------------------------------
int tree[10*maxn];
int a[maxn],cnt1[maxn],cnt2[maxn];
int n,q;
//-------------------------------
void st_build(int l, int r, int vertex);
int st_ans(int l, int r, int i, int j, int vertex);
//-------------------------------
int main() {
 while (true)
 {
  cin >> n >> q;
  if (n==0) break;
  for (int i=1; i<=n; i++) cin >> a[i];
  cnt1[1] = 1;
  for (int i=2; i<=n; i++)
   if (a[i]!=a[i-1]) cnt1[i] = 1;
   else cnt1[i] = cnt1[i-1]+1;
  cnt2[n] = 1;
  for (int i=n-1; i>=1; i--)
   if (a[i]!=a[i+1]) cnt2[i] = 1;
   else cnt2[i] = cnt2[i+1]+1;
  st_build(1,n,1);
  for (int i=1; i<=q; i++)
  {
   int u; int v;
   cin >> u >> v;
   cout << st_ans(1,n,u,v,1) << endl;
  }
 }
 return 0;
}
//-------------------------------
void st_build(int l, int r, int vertex) {
 if (l==r) tree[vertex] = 1;
 else
 {
  int mid = (l+r)/2;
  st_build(l,mid,vertex*2);
  st_build(mid+1,r,vertex*2+1);
  if (a[mid]==a[mid+1])
  {
   int tmp1, tmp2;
   if (abs(mid-l+1)>cnt1[mid]) tmp1 = cnt1[mid];
   else tmp1 = cnt1[mid]-cnt1[l]+1;
   if (abs(r-(mid+1)+1)>cnt2[mid+1]) tmp2 = cnt2[mid+1];
   else tmp2 = cnt2[mid+1]-cnt2[r]+1;
   tree[vertex] = max(max(tree[vertex*2],tree[vertex*2+1]),tmp1+tmp2);
  }
  else tree[vertex] = max(tree[vertex*2],tree[vertex*2+1]);
 }
}
//-------------------------------
int st_ans(int l, int r, int i, int j, int vertex) {
 if (i>r || j<l) return(-1);
 if (l>=i && r<=j) return(tree[vertex]);

 int mid = (l+r)/2;
 int p1 = st_ans(l,mid,i,j,vertex*2);
 int p2 = st_ans(mid+1,r,i,j,vertex*2+1);

 if (p1==-1) return(p2);
 if (p2==-1) return(p1);

 if (a[mid]==a[mid+1]) 
 {
  int tmp1, tmp2;
  if (abs(mid-max(l,i)+1)>cnt1[mid]) tmp1 = cnt1[mid];
  else tmp1 = cnt1[mid]-cnt1[max(l,i)]+1;
  if (abs(min(r,j)-(mid+1)+1)>cnt2[mid+1]) tmp2 = cnt2[mid+1];
  else tmp2 = cnt2[mid+1]-cnt2[min(r,j)]+1;
  return(max((tmp1+tmp2),max(p1,p2)));
 }
 else return(max(p1,p2));
}
//-------------------------------