Rt，本机不开o2只用3s，#2#8TLE。

估计是使用高峰期的原因。

#include<cstdio>
#include<cmath>
#define max(a,b) (a>b?a:b)
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define pre(i,a,b) for(register int i=a;i>=b;i--) 
#define N 20005005
int v[N],pos[N]; 
int l[N],r[N],Max[6300],f[6300][6300];
void swap(int &x,int &y){int t=x;x=y;y=t;}
long long ed=0;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
int n,m,s;
int main()
{
    scanf("%d%d%d",&n,&m,&s);srand(s);
    for(int i=1;i<=n;i++)v[i]=read();
    //rep(i,1,n)printf("%d\n",v[i]);
    int len=pow(n,0.48);
    int bas=n/len+(n%len?1:0);
	//printf("%d %d\n",len,bas);system("PAUSE");
	rep(i,1,n){
        pos[i]=(i-1)/len+1;
        if(i%len==1)l[i]=v[i];
        else l[i]=max(l[i-1],v[i]);
    }
    pre(i,n,1)
        if(pos[i]!=pos[i+1])r[i]=v[i];
        else r[i]=max(v[i],r[i+1]);
    rep(i,1,bas)
      for(int j=(i-1)*len+1;j<=i*len;j++)
        Max[i]=max(Max[i],v[j]);
    rep(i,1,bas)
      f[i][i-1]=0;
    rep(i,1,bas)
      rep(j,i,bas)
        f[i][j]=max(f[i][j-1],Max[j]);
    register int L,R,ans;
    rep(i,1,n){
        L=read()%n+1,R=read()%n+1,ans=0;
        if(L>R)swap(L,R);
        if(pos[L]==pos[R]){
            for(int i=L;i<=R;i++)
              ans=max(ans,v[i]); 
        }
        else ans=max(f[pos[L]+1][pos[R]-1],max(r[L],l[R]));
       	ed+=ans;
    }
    printf("%lld\n",ed);
    return 0;
 }
 /*
 20000000 20000000 233
 */