记录编号	397644	评测结果	AAAAAAAAAAAAAAAAAA
题目名称	[USACO Jan07] 均衡队形	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.238 s
提交时间	2017-04-20 19:54:55	内存使用	7.22 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <cctype>
#include <vector>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;}
  inline int readint(){
    char c; int r; bool s = false;
    while(c = readc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
  }
}; using IO::readint;
int f[50002][17];
int g[50002][17];
int logt[50002];
int main(){
  freopen("lineup.in", "r", stdin);
  freopen("lineup.out", "w", stdout);
  int n = readint();
  int m = readint();
  for(int i = 1; i <= n; i++)
    g[i][0] = f[i][0] = readint();
  for(int k = 1; (1<<k) <= n; k++){
    for(int i = 1; i+(1<<k)-1 <= n; i++){
      int j = k-1;
      f[i][k] = max(f[i][j], f[i+(1<<j)][j]);
      g[i][k] = min(g[i][j], g[i+(1<<j)][j]);
    }
  }
  int logv = 0;
  for(int i = 1; i <= n; i <<= 1)logt[i] = logv++;
  for(int i = 2; i <= n; i++)if(!logt[i])logt[i] = logt[i-1];
  while(m--){
    int l = readint(); int r = readint();
    int s = logt[r-l+1];
    printf("%d\n", max(f[l][s], f[r-(1<<s)+1][s])-min(g[l][s], g[r-(1<<s)+1][s]));
  }
  return 0;
}