The shorter, the simpler. With this problem, you should be convinced of this truth.

You are given an array A of N postive integers, and M queries in the form (l,r). A function F(l,r) (1≤l≤r≤N) is defined as:
F(l,r)={AlF(l,r−1) modArl=r;l<r.
You job is to calculate F(l,r), for each query (l,r)
.
Input
There are multiple test cases.

  The first line of input contains a integer T, indicating number of test cases, and T test cases follow.

For each test case, the first line contains an integer N(1≤N≤100000).
The second line contains N space-separated positive integers: A1,…,AN (0≤Ai≤109).
The third line contains an integer M denoting the number of queries.
The following M lines each contain two integers l,r (1≤l≤r≤N)
, representing a query.
Output
For each query(l,r), output F(l,r)
on one line.
Sample Input

1
3
2 3 3
1
1 3

Sample Output

2

解题报告：自己暴力没过，以为是记忆化搜索，看了大佬的思路结果可以用单调栈维护每个点后面离他最近的比他小的点的坐标。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const	int N=1e5+10;
int a[N];
int b[N];
int main()
{
   
	int t;
	scanf("%d",&t);
	while(t--)
	{
   
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
		stack<int>s;
		for(int i=n;i>=1;i--)
		{
   
			while(s.size()&&a[s.top()]>a[i])
			s.pop();
			if(s.empty())	
			b[i]=n+1;
			else
			b[i]=s.top(); 	
			s.push(i);
		}
		int m;
		scanf("%d",&m);
		while(m--)
		{
   
			int l,r;
			scanf("%d%d",&l,&r);
			ll ans=a[l];
			int pos=b[l];
			while(pos<=r)
			{
   
				if(pos==n+1)	break;
				ans%=a[pos];
				pos=b[pos];
			}
			printf("%lld\n",ans);
		}
	}
    return 0;
}