최소값과 최대값

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);

		String[] line1 = br.readLine().split(" ");
		int N = Integer.parseInt(line1[0]);
		int M = Integer.parseInt(line1[1]);

		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		int height = (int) Math.ceil(getTreeHeight(N));
		int[][] tree = new int[1 << (height+1)][2];
		init(arr, tree, 1, 0, N - 1); // 최대값 init
		init_Min(arr, tree, 1, 0, N - 1); // 최소값 init

		for (int i = 0; i < M; i++) {
			String[] line2 = br.readLine().split(" ");
			int a = Integer.parseInt(line2[0]);
			int b = Integer.parseInt(line2[1]);
			int min = search_min(tree, 1, 0, arr.length-1, a-1, b-1);
			int max = search_max(tree, 1, 0, arr.length-1, a-1, b-1);
			pw.println(min+" "+max);
			pw.flush();
		}
	}

	public static double getTreeHeight(long num) {
		return Math.log10(num) / Math.log10(2);
	}

	public static int init(int[] arr, int[][] tree, int node, int start, int end) {
		if (start == end) {
			return tree[node][0] = arr[start];
		}
		int mid = (start + end) / 2;
		return tree[node][0] = Math.max(init(arr, tree, 2 * node, start, mid),
				init(arr, tree, (2 * node) + 1, mid + 1, end));
	}

	public static int init_Min(int[] arr, int[][] tree, int node, int start, int end) {
		if (start == end) {
			return tree[node][1] = arr[start];
		}
		int mid = (start + end) / 2;
		return tree[node][1] = Math.min(init_Min(arr, tree, 2 * node, start, mid),
				init_Min(arr, tree, (2 * node) + 1, mid + 1, end));
	}

	public static int search_min(int[][] tree, int node, int start, int end, int left, int right) {
		if (right < start || end < left) {
			return 1000000001;
		}
		if (left <= start && end <= right) {
			return tree[node][1];
		}
		int mid = (start + end) / 2;
		return Math.min(search_min(tree, 2 * node, start, mid, left, right),
				search_min(tree, 2 * node + 1, mid + 1, end, left, right));
	}

	public static int search_max(int[][] tree, int node, int start, int end, int left, int right) {
		if (right < start || end < left) {
			return 0;
		}
		if (left <= start && end <= right) {
			return tree[node][0];
		}
		int mid = (start + end) / 2;
		return Math.max(search_max(tree, 2 * node, start, mid, left, right),
				search_max(tree, 2 * node + 1, mid + 1, end, left, right));
	}
}