网络赛的水实在太深，这场居然没出线zzz，差了一点点，看到这道题的的时候就剩半个小时了。上面是官方的题意题解，打完了才知道暴力就可以过，暴力我们当时是想出来了的，如果稍稍再优化一下估计就过了zzz。去年有一场现场赛也是n=1000，n^3过了，看来关键时刻实在做不出来就得大胆暴力啊。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
int a[maxn],nex[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
for(int i=; i<=n; i++)
scanf("%d",&a[i]);
for(int i=; i<=n; i++)
{
nex[i]=-;
for(int j=i+; j<=n; j++)
if(a[j]<=a[i])
{
nex[i]=j;
break;
}
}
int q;
scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);
int ans=a[l];
for(int i=nex[l]; i<=r; i=nex[i])
{
if(i==-)break;
ans%=a[i];
}
printf("%d\n",ans);
}
} return ;
}