1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 typedef pair<int,pair<int,int> > pp;
  6 const int N = 501000;
  7 
  8 int read(){
  9     int x = 0;char ch = getchar();
 10     while (ch < ‘0‘ || ‘9‘ < ch) ch = getchar();
 11     while (‘0‘ <= ch && ch <= ‘9‘) x = x * 10 + ch - ‘0‘,ch = getchar();
 12     return x;
 13 }
 14 
 15 pp seg[N<<2];
 16 int mx[N<<2];
 17 struct Node{
 18     int x,y;
 19     Node(){}
 20     Node(int x,int y):x(x),y(y){}
 21 }nod[N],sta[N];
 22 struct Node2{
 23     int x,y,z;
 24     Node2(){}
 25     Node2(int x,int y,int z):x(x),y(y),z(z){}
 26 }ques[N];
 27 
 28 int n,q,a[N],len,cnt,ans[N];
 29 void init(int,int,int);
 30 void update(int);
 31 void insert(int,int,int,int,int);
 32 int getans(int,int,int,int,int);
 33 pp get(int,int,int,int,int);
 34 pp merge(pp,pp);
 35 bool cmp1(const Node &a,const Node &b){
 36     return a.x < b.x;
 37 }
 38 bool cmp2(const Node &a,const Node &b){
 39     return a.y < b.y;
 40 }
 41 bool cmp3(const Node2 &a,const Node2 &b){
 42     return a.x > b.x;
 43 }
 44 bool cmp4(const Node2 &a,const Node2 &b){
 45     return a.y < b.y;
 46 }
 47 bool cmp5(const Node &a,const Node &b){
 48     return a.x > b.x;
 49 }
 50 
 51 int main(){
 52     n = read();q = read();
 53     for (int i = 1;i <= n;i++) {
 54         a[i] = read();
 55         nod[i] = Node(a[i],i);
 56     }
 57     for (int i = 1;i <= q;i++){
 58         int x,y;x = read();y = read();
 59         ques[i] = Node2(x,y,i);
 60     }
 61     sort(nod+1,nod+1+n,cmp1);
 62     int ncnt = 1;
 63     for (int i = 2;i <= n;i++)
 64         if (nod[i].x == nod[i-1].x) nod[i-1].x = ncnt;
 65         else nod[i-1].x = ncnt++; 
 66     nod[n].x = ncnt;
 67     for (int i = 1;i <= n;i++)
 68         a[nod[i].y] = nod[i].x;
 69     
 70     init(1,1,n);
 71     
 72     
 73     len = 1;sta[1] = Node(a[1],1);cnt = 0;
 74     for (int i = 2;i <= n;i++) {
 75         while (len && a[i] > sta[len].x){
 76             int u = sta[len].x,v = sta[len].y;len--;
 77             while (len && sta[len].x == u){
 78                 nod[++cnt] = Node(sta[len].y,v);
 79                 len--;
 80             }
 81         }
 82         sta[++len] = Node(a[i],i);
 83     }
 84     while (len){
 85         int u = sta[len].x,v = sta[len].y;len--;
 86         while (len && sta[len].x == u){
 87             nod[++cnt] = Node(sta[len].y,v); 
 88             len--;
 89         }
 90     }
 91     
 92     sort(nod+1,nod+1+cnt,cmp2);
 93     sort(ques+1,ques+1+q,cmp4);
 94     int head1 = 1,head2 = 1;
 95     memset(mx,0,sizeof(mx));
 96     for (int i = 1;i <= n;i++){
 97         while (head1 <= cnt && nod[head1].y == i){
 98             int u = nod[head1].x;
 99             insert(1,1,n,u,i-u+1);
100             head1++;
101         }
102         while (head2 <= q && ques[head2].y == i){
103             int x = ques[head2].x,z = ques[head2].z;
104             ans[z] = max(ans[z],getans(1,1,n,x,i));
105             head2++;
106         }
107     }
108     
109     //part2
110     
111     len = 1;sta[1] = Node(a[n],n);cnt = 0;
112     for (int i = n-1;i >= 1;i--) {
113         while (len && a[i] > sta[len].x){
114             int u = sta[len].x,v = sta[len].y;len--;
115             while (len && sta[len].x == u){
116                 nod[++cnt] = Node(v,sta[len].y);
117                 len--;
118             }
119         }
120         sta[++len] = Node(a[i],i);
121     }
122     while (len){
123         int u = sta[len].x,v = sta[len].y;len--;
124         while (len && sta[len].x == u){
125             nod[++cnt] = Node(v,sta[len].y); 
126             len--;
127         }
128     }
129     
130     sort(nod+1,nod+1+cnt,cmp5);
131     sort(ques+1,ques+1+q,cmp3);
132     head1 = 1;head2 = 1;
133     memset(mx,0,sizeof(mx));
134     for (int i = n;i >= 1;i--){
135         while (head1 <= cnt && nod[head1].x == i){
136             int u = nod[head1].y;
137             insert(1,1,n,u,u-i+1);
138             head1++;
139         }
140         while (head2 <= q && ques[head2].x == i){
141             int y = ques[head2].y,z = ques[head2].z;
142             ans[z] = max(ans[z],getans(1,1,n,i,y));
143             head2++;
144         }
145     }
146     
147     
148 //    part3
149     for (int i = 1;i <= q;i++){
150         int x = ques[i].x,y = ques[i].y,z = ques[i].z;
151         pp g = get(1,1,n,x,y);
152         ans[z] = max(ans[z],g.second.second - g.second.first + 1);
153         /*
154             如果单个点不算答案，这里要特判无解 
155             否则恰好包含单个点的情况（原来没考虑到 
156         */
157     }
158     for (int i = 1;i <= q;i++) printf("%d\n",ans[i]);
159     return 0;
160 }
161 void init(int p,int l,int r){
162     if (l == r){
163         seg[p].first = a[l];
164         seg[p].second = make_pair(l,l);
165         return;
166     }
167     int mid = l + r >> 1;
168     init(p<<1,l,mid);
169     init(p<<1|1,mid+1,r);
170     update(p);
171 }
172 void update(int p){
173     int u = p<<1,v = u|1;
174     if (seg[u].first < seg[v].first) seg[p] = seg[v];
175     else if (seg[u].first > seg[v].first) seg[p] = seg[u];
176     else{
177         seg[p].first = seg[u].first;
178         seg[p].second.first = seg[u].second.first;
179         seg[p].second.second = seg[v].second.second;
180     }
181 }
182 void insert(int p,int l,int r,int x,int y){
183     mx[p] = max(mx[p],y);
184     if (l == r) return;
185     int mid = l + r >> 1;
186     if (x <= mid) insert(p<<1,l,mid,x,y);
187     else insert(p<<1|1,mid+1,r,x,y);
188 }
189 int getans(int p,int l,int r,int x,int y){
190     if (l == x && r == y) return mx[p];
191     int mid = l + r >> 1;
192     if (y <= mid) return getans(p<<1,l,mid,x,y);
193     else if (mid < x) return getans(p<<1|1,mid+1,r,x,y);
194     else return max(getans(p<<1,l,mid,x,mid),getans(p<<1|1,mid+1,r,mid+1,y));
195 }
196 pp get(int p,int l,int r,int x,int y){
197     if (l == x && r == y) return seg[p];
198     int mid = l + r >> 1;
199     if (y <= mid) return get(p<<1,l,mid,x,y);
200     else if (mid < x) return get(p<<1|1,mid+1,r,x,y);
201     else return merge(get(p<<1,l,mid,x,mid),get(p<<1|1,mid+1,r,mid+1,y));
202 }
203 pp merge(pp x,pp y){
204     pp z;
205     if (x.first > y.first) return x;
206     else if (x.first < y.first) return y;
207     else {
208         z.first = x.first;
209         z.second.first = x.second.first;
210         z.second.second = y.second.second;
211         return z;
212     }
213 }