BOJ 2357

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
#define MAXN 100001
#define INF 1000000001
int arr[MAXN];
vector<int> min_tree;
vector<int> max_tree;
int N,M;

int init(vector<int>& tree, int node, int start, int end, int mode){
    if (start == end) return tree[node] = arr[start];
    int mid = (start+end)/2;
    if (mode==0){
        return tree[node] = min(init(tree,node*2,start,mid,mode),init(tree,node*2+1,mid+1,end,mode));
    }
    else{
        return tree[node] = max(init(tree,node*2,start,mid,mode),init(tree,node*2+1,mid+1,end,mode));
    }
}
int calc(vector<int>& tree, int node, int start, int end, int left, int right, int mode){
    if (left> end || right < start) {
        // 최솟값 구할 경우 INF로 리턴
        if (mode ==0) return INF;
        // 최댓값 구할 경우 0으로 리턴
        else return 0;
    }
    if (left <= start && end <= right) return tree[node];
    int mid = (start + end) / 2;
    if (mode==0){
        return min(calc(tree,node*2,start,mid,left,right,mode),calc(tree,node*2+1,mid+1,end,left,right,mode));
    }
    else{
        return max(calc(tree,node*2,start,mid,left,right,mode),calc(tree,node*2+1,mid+1,end,left,right,mode));
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 0; i <N;i++){
        cin >> arr[i];
    }
    int h = 1;
    while (h < N) h <<= 1;
    min_tree = vector<int>(h*2);
    max_tree = vector<int>(h*2);
    init(min_tree,1,0,N-1,0);
    init(max_tree,1,0,N-1,1);
    while (M--){
        int left,right;
        cin >> left >> right;
        left--;
        right--;
        cout << calc(min_tree,1,0,N-1,left,right,0) << " " << calc(max_tree,1,0,N-1,left,right,1) <<"\n";
    }
    return 0;
}