RANGE_MINIMUM_QUERY

RMQSQ - Range Minimum Query

no tags 

You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the minimum number between the range [i, j] (inclusive).

Note: the query ranges are specified using 0-based indexing.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Example

Input:
3
1 4 1
2
1 1
1 2

Output:
4
1

#####################################################CODE############################################

#include<iostream>
using namespace std;
int arr[1010000];
int tree[1010000];
int laz[10100000];
#define inf 999999999
int query(int node,int start,int end,int r1,int r2)
 {
  // cout<<start<<" "<<end<<endl;
 
   if(laz[node])
   {
     tree[node]+=laz[node];
     laz[2*node]+=laz[node];
     laz[2*node+1]+=laz[node];
     laz[node]=0;
   }

 if(start>end || r1>end || r2<start) return inf;

   if(r1<=start && r2>=end)
    {
     return tree[node];
     
    }
    else
    {
     int q1=query(2*node,start,(start+end)/2,r1,r2);
     int q2=query(2*node+1,((start+end)/2)+1,end,r1,r2);
     return min(q1,q2);
    }
 }
void update(int node ,int start,int end,int r1,int r2,int val)
 {

  if(laz[node]!=0)
   {
    
    tree[node]+=laz[node];
    laz[2*node+1]+=laz[node];
    laz[2*node]+=laz[node];
    laz[node]=0;
   }
    if(r1>end  || r2<start   || start>end) return  ;

  if(r1<=start && r2>=end)
   {
     tree[node]+=val;
     if(start!=end)
      {
       laz[2*node]+=val;
       laz[2*node+1]+=val;
       
      }
      return  ;
   }
    update(2*node, start,(start+end)/2,r1,r2,val);
    update(2*node+1, ((start+end)/2)+1,end,r1,r2,val);
   tree[node]=min(tree[2*node],tree[2*node+1]);
   
 }
void build(int node , int start,int end)
 {
  if(start==end) tree[node]=arr[start];
  else if(start>end) return ;
  else
   {
    build(2*node,start,(start+end)/2);
    build(2*node+1,((start+end)/2)+1,end);
    tree[node]=min(tree[2*node],tree[2*node+1]);
   }
   
 }
int main()
 {
  
   int n;
    cin>>n;
     for(int i=0;i<n;i++)
       cin>>arr[i];
       build(1,0,n-1);
   //    for(int i=0;i<20;i++) cout<<i<<" "<<tree[i]<<endl;
       
      int q;
       cin>>q;
        while(q--)
         {
          int ip;
           //cin>>ip;
           /*if(ip==0)
            {
             int r1,r2,val;
              cin>>r1>>r2>>val;
              update(1,0,n-1,r1,r2,val);
            }
            else*/
             {
              int r1,r2;
               cin>>r1>>r2;
              int res= query(1,0,n-1,r1,r2);
               cout<<res<<endl;
             }
         }
       
  return 0;
 }