/*
Range Minimum Query in < O(n), O(1) > implementation - Bogdan Iordache 2015
*/

#include <fstream>
#include <vector>
#include <stack>



//a data structure that returns the minimum value from a given sequence
template < class myClass >
class RangeMinimumQuery {

private:

	std::vector<myClass> data; //the given array of values

	//from now on every element saved in the future data structures represents the index of the element in the initial array, not the value

	std::vector< std::vector<int> > blocks; //the blocks and their Sparse Table in which the array is segmentated
	std::vector<int> minBlock; //an array that is used to return quickly the minimum from a sequence in a block
	std::vector<int> leftBit; //keeps the position of the most left-placed bit in a number, indexed from left and has a length of lg bits (see lg description)

	int n; //the length of the initial array
	int lg; //the length of a block

	//returns the index of the lesser element
	int min(int firstIndex, int secondIndex) {

		return (data[firstIndex] > data[secondIndex] ? secondIndex : firstIndex);

	}

public:

	RangeMinimumQuery() {}

	RangeMinimumQuery(std::vector<myClass> insertArray) {

		data = insertArray;
		n = data.size();

		lg = 0; //lg is equal to log[2](n);

		while ((1 << lg) <= n)
			++lg;

		blocks.resize((n + lg - 1) / lg, std::vector<int>(lg, 0)); //initialises the blocks and their ST

		//compute the blocks' ST

		for (int i = 0; i < n; ++i) {

			if (i % lg == 0)
				blocks[i / lg][0] = i;

			blocks[i / lg][0] = min(blocks[i / lg][0], i);

		}

		for (int j = 1; j < lg; ++j) {

			for (unsigned int i = 0; i < blocks.size(); ++i) {

				blocks[i][j] = blocks[i][j - 1];

				if (i + (1 << (j - 1)) < blocks.size())
					blocks[i][j] = min(blocks[i][j], blocks[i + (1 << (j - 1))][j - 1]);


			}

		}

		minBlock.resize(n, 0); //initialises the minBlock

		//compute the minBlock

		for (unsigned int i = 0; i < blocks.size(); ++i) {

			std::stack<int> st;

			//this computation simulates the contruction of a Cartesian Tree

			for (unsigned int j = i * lg; j < i * lg + lg && j < n; ++j) {

				while (!st.empty() && data[j] < data[st.top()])
					st.pop();

				minBlock[j] = (1 << (i * lg - j + lg - 1)); //the bit corresponding to j is 1 and for the lesser element in front of it we have them marked with 0

				if (!st.empty())
					minBlock[j] |= minBlock[st.top()]; //combines the result with the previous calculations

				st.push(j);

			}

		}

		leftBit.resize((1 << lg), 0); //initialises the leftBit

		//compute the leftBit

		for (int i = 1, current = lg - 1; i < (1 << lg); ++i) {

			if ((1 << (lg - current)) <= i)
				current--;

			leftBit[i] = current;

		}

	}

	//returns the minimum value from sequence left-right
	myClass getMin(int left, int right) {
		
		int leftBlock = left / lg + 1; //the block at the right of the block of 'left'
		int rightBlock = right / lg - 1; //the block at the left of the block of 'right'

		int ans = left; //initialises the answer with the position of 'left'

		//computes the minimum value between leftBlock and rightBlock, exclusively
		if (leftBlock <= rightBlock) {

			int temp = lg - leftBit[rightBlock - leftBlock + 1] - 1;

			ans = min(ans, min(blocks[leftBlock][temp], blocks[rightBlock - (1 << temp) + 1][temp]));

		}

		//computes the minimum value from the left block-segment

		int temp = (leftBlock * lg - 1 < right ? leftBlock * lg - 1 : right);

		ans = min(ans, leftBit[minBlock[temp] & (~(((1 << (left - (leftBlock - 1) * lg)) - 1) << (leftBlock * lg - left)))] + (leftBlock - 1) * lg);

		//computes the minimum value from the right block-segment

		temp = right;

		left = ((rightBlock + 1) * lg < left ? left : (rightBlock + 1) * lg);

		ans = min(ans, leftBit[minBlock[temp] & (~(((1 << (left - (rightBlock + 1) * lg)) - 1) << ((rightBlock + 2) * lg - left)))] + (rightBlock + 1) * lg);

		//returns the minimum value
		return data[ans];

	}

};


int main() {

	std::ifstream fin("rmq.in");
	std::ofstream fout("rmq.out");

	int n, queryCount;

	fin >> n >> queryCount;

	std::vector<int> vec;

	for (int i = 1; i <= n; ++i) {

		int x;

		fin >> x;

		vec.push_back(x);

	}

	RangeMinimumQuery<int> *rangeMinimumQuery = new RangeMinimumQuery<int>(vec);

	while (queryCount--) {

		int qLeft, qRight;

		fin >> qLeft >> qRight;

		fout << rangeMinimumQuery->getMin(qLeft - 1, qRight - 1) << '\n';

	}

	return 0;

}

//Trust me, I'm the Doctor!