package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	buf := make([]byte, 1024*1024)
	scanner.Buffer(buf, 10*1024*1024)

	nextInt := func() int {
		scanner.Scan()
		val, _ := strconv.Atoi(scanner.Text())
		return val
	}

	n := nextInt()
	q := nextInt()

	A := make([]int, n)
	for i := 0; i < n; i++ {
		A[i] = nextInt()
	}

	S := make([][]int, 0)
	S = append(S, make([]int, n))
	for i := 0; i < n; i++ {
		S[0][i] = i
	}

	currOp := 0
	for len(S[len(S)-1]) > 1 {
		prev := S[len(S)-1]
		var next []int
		for i := 0; i < len(prev); i++ {
			val := A[prev[i]]
			isOk := true
			if i > 0 {
				leftVal := A[prev[i-1]]
				if currOp == 0 && val >= leftVal {
					isOk = false
				}
				if currOp == 1 && val <= leftVal {
					isOk = false
				}
			}
			if i < len(prev)-1 {
				rightVal := A[prev[i+1]]
				if currOp == 0 && val >= rightVal {
					isOk = false
				}
				if currOp == 1 && val <= rightVal {
					isOk = false
				}
			}
			if isOk {
				next = append(next, prev[i])
			}
		}
		S = append(S, next)
		currOp = 1 - currOp
	}

	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	buffer := make([]int, 0, 60)
	nextPref := make([]int, 0, 40)
	nextSuff := make([]int, 0, 40)
	statePref := make([]int, 0, 40)
	stateSuff := make([]int, 0, 40)

	for i := 0; i < q; i++ {
		l := nextInt() - 1
		r := nextInt() - 1

		idx1 := sort.Search(len(S[0]), func(j int) bool { return S[0][j] >= l })
		idx2 := sort.Search(len(S[0]), func(j int) bool { return S[0][j] > r }) - 1

		statePref = statePref[:0]
		stateSuff = stateSuff[:0]
		stateL := idx1
		stateR := idx2
		k := 0
		op := 0

		for {
			totalSize := len(statePref) + len(stateSuff)
			if stateL <= stateR {
				totalSize += stateR - stateL + 1
			}
			if totalSize <= 1 {
				break
			}

			if stateL <= stateR && stateR-stateL+1 <= 10 {
				for j := stateL; j <= stateR; j++ {
					statePref = append(statePref, S[k][j])
				}
				statePref = append(statePref, stateSuff...)
				stateSuff = stateSuff[:0]
				stateL = 1
				stateR = 0
			}

			if stateL <= stateR {
				statePref = append(statePref, S[k][stateL], S[k][stateL+1])
				stateL += 2

				buffer = buffer[:0]
				buffer = append(buffer, S[k][stateR-1], S[k][stateR])
				buffer = append(buffer, stateSuff...)
				stateSuff = append(stateSuff[:0], buffer...)
				stateR -= 2
			}

			nextPref = nextPref[:0]
			for j := 0; j < len(statePref); j++ {
				val := A[statePref[j]]
				isOk := true
				if j > 0 {
					leftVal := A[statePref[j-1]]
					if op == 0 && val >= leftVal {
						isOk = false
					}
					if op == 1 && val <= leftVal {
						isOk = false
					}
				}
				if j < len(statePref)-1 {
					rightVal := A[statePref[j+1]]
					if op == 0 && val >= rightVal {
						isOk = false
					}
					if op == 1 && val <= rightVal {
						isOk = false
					}
				} else if stateL <= stateR {
					rightVal := A[S[k][stateL]]
					if op == 0 && val >= rightVal {
						isOk = false
					}
					if op == 1 && val <= rightVal {
						isOk = false
					}
				} else if len(stateSuff) > 0 {
					rightVal := A[stateSuff[0]]
					if op == 0 && val >= rightVal {
						isOk = false
					}
					if op == 1 && val <= rightVal {
						isOk = false
					}
				}
				if isOk {
					nextPref = append(nextPref, statePref[j])
				}
			}

			nextSuff = nextSuff[:0]
			for j := 0; j < len(stateSuff); j++ {
				val := A[stateSuff[j]]
				isOk := true
				if j > 0 {
					leftVal := A[stateSuff[j-1]]
					if op == 0 && val >= leftVal {
						isOk = false
					}
					if op == 1 && val <= leftVal {
						isOk = false
					}
				} else if stateL <= stateR {
					leftVal := A[S[k][stateR]]
					if op == 0 && val >= leftVal {
						isOk = false
					}
					if op == 1 && val <= leftVal {
						isOk = false
					}
				} else if len(statePref) > 0 {
					leftVal := A[statePref[len(statePref)-1]]
					if op == 0 && val >= leftVal {
						isOk = false
					}
					if op == 1 && val <= leftVal {
						isOk = false
					}
				}
				if j < len(stateSuff)-1 {
					rightVal := A[stateSuff[j+1]]
					if op == 0 && val >= rightVal {
						isOk = false
					}
					if op == 1 && val <= rightVal {
						isOk = false
					}
				}
				if isOk {
					nextSuff = append(nextSuff, stateSuff[j])
				}
			}

			newL := 1
			newR := 0
			if stateL <= stateR {
				startVal := S[k][stateL]
				endVal := S[k][stateR]

				i1 := sort.Search(len(S[k+1]), func(idx int) bool {
					return S[k+1][idx] >= startVal
				})
				i2 := sort.Search(len(S[k+1]), func(idx int) bool {
					return S[k+1][idx] > endVal
				}) - 1

				if i1 <= i2 {
					newL = i1
					newR = i2
				}
			}

			statePref = append(statePref[:0], nextPref...)
			stateSuff = append(stateSuff[:0], nextSuff...)
			stateL = newL
			stateR = newR

			k++
			op = 1 - op
		}

		var ansIdx int
		if len(statePref) > 0 {
			ansIdx = statePref[0]
		} else if len(stateSuff) > 0 {
			ansIdx = stateSuff[0]
		} else {
			ansIdx = S[k][stateL]
		}

		fmt.Fprintln(out, A[ansIdx])
	}
}