You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the 
query.

The last test case is followed by a line containing a single 0.

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

#include<stdio.h>

#define MAX_N 500000

struct node{
	int l;
	int r;
	int max;
};
struct msg{
	int value;
	int start;
	int end;
};
node tree[3*MAX_N];
int a[MAX_N+5];
int b[MAX_N+5];
int c[MAX_N+5];
msg inv[MAX_N+5];

int max(int x,int y){
	if(x>y)
		return x;
	else
		return y;
}

void swap(int &s,int &e){
	s=s^e;
	e=s^e;
	s=s^e;
}

void build_tree(int left,int right,int root){
	tree[root].l=left;
	tree[root].r=right;
	if(left==right){
		tree[root].max=b[left];
		return;
	}
	int mid=(left+right)/2;
	build_tree(left,mid,root*2);
	build_tree(mid+1,right,root*2+1);
	tree[root].max=max(tree[root*2].max,tree[root*2+1].max);
}

int find_max(int left,int right,int root){
	if(left==tree[root].l&&right==tree[root].r)
		return tree[root].max;
	int mid=(tree[root].l+tree[root].r)/2;
	if(right<=mid)
		return find_max(left,right,root*2);
	else if(left>mid)
		return find_max(left,right,root*2+1);
	else
		return max(find_max(left,mid,root*2),find_max(mid+1,right,root*2+1));
}

int main(){
	int n,m,i,len,inv_len,s,e;
	while(scanf("%d",&n)!=EOF){
		if(n==0)
			break;
		scanf("%d",&m);
		for(i=1;i<=n;i++)
			scanf("%d",&a[i]);
		len=0,inv_len=0;
		b[++len]=1;
		c[1]=1;
		inv[++inv_len].value=http://www.mamicode.com/a[1];>