/* Algoritm problema "RMQ"

   E tot algoritmul tip "RMQ", numai ca foarte optimizat (dar cam muncitoresc)
   Retinem in vectorul RMQ[] minimul dintre numere astfel:

   din 2 in 2
   din 4 in 4
   ....
   din 2^log2(n) in 2^log2(n)

   La un Query vom cauta binar intervalele care intra in intervalul cerut de ei
   Citire parsata + Iesire parsata

   Multumim Doamne!
*/
/// Bibliotecile care ne trebuiesc
#include <stdio.h>                /// pentru fread() + fwrite() + printf()
#include <ctype.h>                /// pentru isdigit()
#include <limits.h>               /// pentru INT_MAX
#include <math.h>                 /// pentru log2(step)

/// Constantele care ne trebuiesc
#define  Nadejde  100000          /// marimea vectorului
#define  Dragoste 4096            /// marimea buff[] & Buff[]
#define  MAXLOG   16              /// log2(100000)
#define  MAXDIG   6               /// cate cifre poate avea un int
#define  MINSTEP  2               /// intervalul minim

/// Variabiele care ne trebuiesc
int   n;                          /// numarul de elemente din vector
int   i;                          /// un index
int   j;                          /// un index
int   q;                          /// num / 10
int   lo;                         /// folosit la cautarea binara
int   hi;                         /// folosit la cautarea binara
int   up;                         /// lo/hi * step
int   lg;                         /// log2(step)
int   mid;                        /// (up + down)/2
int   num;                        /// numarul minim
int   div;                        /// left/right / step
int   left;                       /// extremitatea stanga a intervalului
int   step;                       /// intervalul de inceput
int   down;                       /// (lo/hi + 1) * step
int   add0;                       /// daca left este divizibil cu interval
int   add1;                       /// daca right este divizibil cu interval
int   save;                       /// salvam intervalul ca sa il putem refolosim
int   right;                      /// extremitatea dreapta a intervalului
int   gasit;                      /// stegulet
int   index;                      /// pozitia in RMQ[]
int   Query;                      /// cate intrebari imi pui?
int   numDIG;                     /// numarul de cifre al rezultatului
int   partial;                    /// pozitia in Sum[]
int   interval;                   /// ne jonglam cu el
int   Sum[MAXLOG + 1];            /// pozitiile in RMQ[]
int   Shoe[Nadejde + 1];          /// vectorul nostru
int   RMQ[ Nadejde + Dragoste ];  /// vectorul de intervale
char  c;                          /// un caracter
char  digits[ MAXDIG ];           /// vectorul cu cifrele numarului
char  buff[ Dragoste ];           /// bufferul oferit de sistem
char  Buff[ Dragoste ];           /// bufferul de iesire
short parse;                      /// pozitia in Buff[]
short pos = Dragoste;             /// pozitia in buff[]

/// fgetc()
char getChar( FILE *fin ) {
    if( pos == Dragoste ) {
        fread(buff , 1 , Dragoste , fin);
        pos = 0;
    }
   return buff[ pos ++ ];
}
/// fscanf()
inline void scanFILE( FILE *fin , int *result ){
    *result = 0;

    do{
        c = getChar( fin );
    }while( !isdigit( c ));

    do{
        *result = (*result << 3) + (*result << 1) + c - '0';
        c = getChar( fin );
    }while( isdigit( c ));
}
/// fputc()
inline void putChar( FILE *fout , char ch ){
    Buff[ parse ++ ] = ch;
    if( parse == Dragoste ){
        fwrite(Buff ,1 , Dragoste, fout);
        parse = 0;
    }
}
/// fprintf()
inline void printFILE( FILE *fout , int num ){
    numDIG = 0;
    do{
        q = num / 10;
        digits[ numDIG ++ ] = num - (q << 3) - (q << 1) + '0';
        num = q;
    }while( num );

    do{
        putChar( fout , digits[ --numDIG ]);
    }while( numDIG );
}
/// golim Buff[]
inline void FlushBuff( FILE *fout ) {
    fwrite( Buff , 1 , parse , fout );
}
/// minimul dintre X si Y
int MIN( int X , int Y ){
    if( X < Y ) {
        return X;
    }
    else{
        return Y;
    }
}
/// precalculam RMQ[] + Sum[]
void Precalculate( ) {
    /// incepem cu intervalul minim
    step = MINSTEP;
    div = n / step;
    div += ( (div * step) != n );
    /// salvam suma
    Sum[ ++partial ] = Sum[ partial - 1 ] + div;
    /// initializam totul cu INT_MAX
    Shoe[ n ] = INT_MAX;
    for( i = 0 ; i < Nadejde + Dragoste ; i ++ ){
        RMQ[ i ] = INT_MAX;
    }
    /// facm RMQ[] din 2 in 2
    for( i = 0 ; i < div ; i ++ ) {
        for( j = 0 ; j < MINSTEP ; j ++ ) {
            RMQ[ i ] = MIN( RMQ[ i ] , Shoe[ i * step + j ]);
        }
    }
    /// salvam mereu index-ul
    index = div;
    /// dublam intervalul
    step <<= 1 ;
    /// cat timp nu e OVERFLOW
    while( step <= n ) {
        /// facem impartirea
        div = n / step;
        /// salvam suma
        Sum[ ++partial ] = Sum[ partial - 1 ] + div + ((div * step) != n);
        /// construim in continuare RMQ[] folosindu-ne de configuratia anterioara
        for( i = 0 ; i < div ; i ++ ) {
            for( j = 0 ; j < MINSTEP ; j ++ ) {
                RMQ[i + index] = MIN( RMQ[i + index] , RMQ[Sum[partial - MINSTEP] + (i * MINSTEP) + j] );
            }
        }
        /// daca e ceva in neregula cu repartitia
        if( n % step ) {
            for( j = div * step ; j < n ; j ++ ){
                RMQ[i + index] = MIN(RMQ[i + index] , Shoe[ j ]);
            }
           div ++;
        }
        /// salvam index-ul
        index += div;
        /// dublam step-ul
        step <<= 1;
    }
   /// cu step-ul acesta incepem
   step >>= 1;
}
/// int main()
int main( ) {
    /// deschidere fisiere *C*
    FILE *fin = fopen( "rmq.in" , "r" );
    FILE *fout = fopen( "rmq.out" , "w" );
    /// citim parsat datele de intrare
    scanFILE( fin , &n );
    scanFILE( fin , &Query );
    /// citim vectorul nostru
    for( i = 0 ; i < n ; i ++ ) {
        scanFILE( fin , &Shoe[ i ] );
    }
    /// Precalculam RMQ[] + Sum[]
    Precalculate( );
    /// salvam intervalul pentru a-l refolosi
    save = step;
    /// citim intrebarile
    while( Query ) {
        /// citim extremitatile intervalului + le decrementam
        scanFILE( fin , &left );
        left --;
        scanFILE( fin , &right );
        right --;
        /// initializam variabilele de care avem nevoie
        add0 = 0;
        add1 = 0;
        num = INT_MAX;
        /// daca intervalul are lungimea cel putin 2
        if(right - left > 1) {
            /// calculam in ce interval se incadreaza left & right
            lo = left / step;
            lo -=((left % step) == 0);
            add0 = (left % step == 0);

            hi = right / step;
            hi += (right % step == step - 1);
            add1 = (right % step == step - 1);
            /// cautam un interval diferit
            while( hi - lo < MINSTEP ) {
                /// injumatatim step-ul
                step >>= 1;
                /// recalculam valorile pentru acest step
                lo = left / step ;
                lo -= ((left % step) == 0 );
                add0 = (left % step == 0 );

                hi = right / step;
                hi += (right % step == step - 1);
                add1 = (right % step == step - 1);
            }
          /// calculam log2(step)
          lg = log2( step );
          /// salvam logaritmul
          partial = lg;
          /// luam minimul din intervalele astfel gasite
          for( i = lo + 1 ; i < hi ; i ++ ) {
            num = MIN( num , RMQ[Sum[lg - 1] + i] );
          }
          /// Analizam left
          /// daca e inceputul unei secvente 2^k nu il bagam in seama
          if( !add0 ) {
            gasit = 0;
            /// calculam variabilele de care avem nevoie
            interval = step;                            /// intervalul cu care pornim pe partea stanga
            down = lo * step;                           /// extremitatea stanga a intervalului
            up = down + step;                           /// extremitatea dreapta a intervalului
            /// cautam minimul dintre intervale
            while( !gasit && interval > MINSTEP ) {
                /// calculam mijlocul + injumatatim intervalul + decrementam lg
                mid = down + ((up - down) >> 1);
                interval >>= 1;
                lg --;
                /// daca e pe partea dreapta
                if(left > mid) {
                    down = mid;
                }
                else {
                    /// daca e pe partea stanga ,am gasit un nou minim?
                    if(left < mid) {
                        up = mid;
                        num = MIN( num , RMQ[Sum[lg - 1] + (left / interval) + 1] );
                    }
                    /// e inceputul unei secvente 2^k + iesim din bucla while()
                    else{
                        gasit = 1;
                        num = MIN( num , RMQ[Sum[lg - 1] + (left / interval)] );
                    }
                 }
              }
            /// daca nu e inceputul unei secvente 2^k si am ajuns la un interval de 2
            if( !gasit && interval == MINSTEP ) {
                /// e pe partea stanga?
                if(down == left) {
                    num = MIN( num , Shoe[ left ] );
                }
                else {
                    /// e pe partea dreapta?
                    if(up == left) {
                        num = MIN( num , Shoe[ left ] );
                    }
                    /// atunci e in mijloc
                    else{
                        num = MIN( num , Shoe[down + ((up - down) >> 1)] );
                    }
                 }
              }
           }
           /// Analizam right
           /// e sfarsitul unei secvente 2^k
            if( !add1 ) {
                gasit = 0;
                interval = step ;                     /// incepem cautarea cu acest interval
                down = hi * step ;                    /// extremitatea stanga a intervalului
                up = down + step ;                    /// extremitatea dreapta a intervalului
                lg = partial ;                        /// salvam lg
                /// cautam intervale noi
                while( !gasit && interval > MINSTEP ) {
                    mid = down + ((up - down) >> 1);  /// calculam mijlocul intervalului
                    interval >>= 1;                   /// injumatatim intervalul
                    lg --;                            /// decrementam lg
                    /// daca e pe partea stanga
                    if( right < mid - 1 ) {
                        up = mid;
                    }
                    else{
                        /// daca e pe partea dreapta
                        if( right > mid - 1 ) {
                            down = mid;
                            num = MIN( num , RMQ[Sum[lg - 1] + (right / interval) - 1 ]);
                        }
                        /// daca e sfarsitul unei secvente 2^k
                        else {
                            gasit = 1;
                            num = MIN( num , RMQ[Sum[lg - 1] + (right / interval)] );
                        }
                    }
                }
               /// daca nu e sfarsitul unei secvente 2^k si intervalul are lungimea 2
               if( !gasit && interval == MINSTEP ) {
                   /// daca e pe stanga
                   if(down == right) {
                    num = MIN( num , Shoe[ right ] );
                   }
                   else{
                    /// daca e pe dreapta
                    if(up == right) {
                        num = MIN( num , Shoe[ right ] );
                    }
                    /// atunci e pe mijloc
                    else{
                        num = MIN( num , Shoe[ down + ((up - down) >> 1) ] );
                    }
                  }
               }
            }
          }
          /// daca lungimea intervalului este de cel mult 1
          else{
            num = MIN( Shoe[ left ] , Shoe[ right ] );
          }
          /// initializam mereu step
          step = save;
          /// afisam rezultatul + mereu linie noua
          printFILE( fout , num );
          putChar( fout , '\n' );
          /// decrementam Query
          Query --;
        }
        /// golim Buff[]
        FlushBuff( fout );
        /// inchidem fisierele
        fclose( fin );
        fclose( fout );
        /// Multumim Doamne!
        printf( "Hristos a inviat!" );
        /// dai return 0
        return 0;
}