Consider an $n$-integer sequence, $A=\{a_0,a_1,\ldots,a_{n-1}\}$. We perform a query on $\mbox{A}$ by using an integer, $\boldsymbol{d}$, to calculate the result of the following expression:

$\underset{0\leq i\leq n-d}{\text{min}}\left(\underset{i\leq j\lt i+d}{\text{max}}a_j\right)$

In other words, if we let $m_i=\text{max}(a_i,a_{i+1},a_{i+2},...,a_{i+d-1})$, then you need to calculate $\text{min}(m_0,m_1,\ldots,m_{n-d})$.  

Given $\textbf{arr}$ and $\textit{q}$ queries, return a list of answers to each query.

Example 

$arr=[2,3,4,5,6]$ 

$queries=[2,3]$  

The first query uses all of the subarrays of length $2$:  $[2,3],[3,4],[4,5],[5,6]$.  The maxima of the subarrays are $[3,4,5,6]$.  The minimum of these is $3$.  

The second query uses all of the subarrays of length $3$: $[2,3,4],[3,4,5],[4,5,6]$.  The maxima of the subarrays are $[4,5,6]$.  The minimum of these is $\begin{array}{c}4\end{array}$.  

Return $[3,4]$.  

Function Description   

Complete the solve function below.  

solve has the following parameter(s):  

int arr[n]: an array of integers  
int queries[q]: the lengths of subarrays to query  

Returns  

int[q]: the answers to each query   

Input Format

The first line consists of two space-separated integers, $n$ and $\textit{q}$. 

The second line consists of $n$ space-separated integers, the elements of $\textbf{arr}$. 

Each of the $\textit{q}$ subsequent lines contains a single integer denoting the value of $\boldsymbol{d}$ for that query. 

Constraints

$1\leq n\leq10^5$
$0\leq ar r[i]<10^6$
$1\leq q\leq100$
$1\leq d\leq n$

Sample Input 0
5 5
33 11 44 11 55
1
2
3
4
5

Sample Output 0
11
33
44
44
55

Explanation 0

For $\boldsymbol{d}=1$, the answer is $\text{min}(\text{max}(a_0),\text{max}(a_1),\text{max}(a_2),\text{max}(a_3),\text{max}(a_4))=11$. 

For $\boldsymbol{d}=2$, the answer is $\text{min}(\text{max}(a_0,a_1),\text{max}(a_1,a_2),\text{max}(a_2,a_3),\text{max}(a_3,a_4))=33$. 

For $\boldsymbol{d}=3$, the answer is $\text{min}(\text{max}(a_0,a_1,a_2),\text{max}(a_1,a_2,a_3),\text{max}(a_2,a_3,a_4))=44$. 

For $\boldsymbol{d}=4$, the answer is $\text{min}(\text{max}(a_0,a_1,a_2,a_3),\text{max}(a_1,a_2,a_3,a_4))=44$. 

For $\boldsymbol{d}=5$, the answer is $\text{min}(\text{max}(a_0,a_1,a_2,a_3,a_4))=55$.  

Sample Input 1
5 5
1 2 3 4 5
1
2
3
4
5

Sample Output 1
1
2
3
4
5

Explanation 1

For each query, the "prefix" has the least maximum value among the consecutive subsequences of the same size.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Data structures


Solutions:
from collections import deque
import heapq
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	q = deque([], d)
	h = []
	for i in range(d):
		while len(q) and l[i] >= l[q[-1]]:
			q.pop()
		q.append(i)
	for i in range(i + 1, len(l)):
		heapq.heappush(h, l[q[0]])
		while len(q) and q[0] <= i - d:
			q.popleft()
		while len(q) and l[i] >= l[q[-1]]:
			q.pop()
		q.append(i)
	heapq.heappush(h, l[q[0]])
	print(h[0])


def Sol(a, d):
	if d == len(a):
		return max(a)
	maxqueue = [0]
	for k in range(1, d):
		while maxqueue and a[k] > a[maxqueue[-1]]:
			maxqueue.pop()
		maxqueue.append(k)
	res = a[maxqueue[0]]
	for k in range(d, len(a)):
		if k - maxqueue[0] >= d:
			maxqueue.pop(0)
		while maxqueue and a[k] > a[maxqueue[-1]]:
			maxqueue.pop()
		maxqueue.append(k)
		res = min(res, a[maxqueue[0]])
	return res
(N, Q) = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(Q):
	d = int(input())
	print(Sol(a, d))


from collections import deque
from heapq import heappush, heappop
(N, Q) = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
for _ in range(Q):
	size = int(input())
	q = deque()
	low = 0
	high = low + size
	arr_l = len(arr)
	initial = arr[low:high]
	q = deque(initial)
	highest = []
	for (i, val) in enumerate(initial):
		heappush(highest, (-val, i))
	min_max_val = -highest[0][0]
	pos = highest[0][1]
	while high < arr_l:
		while low >= pos:
			if highest:
				heappop(highest)
			else:
				break
			if highest:
				pos = highest[0][1]
		heappush(highest, (-arr[high], high))
		pos = highest[0][1]
		if -highest[0][0] < min_max_val:
			min_max_val = -highest[0][0]
		low += 1
		high += 1
	print(min_max_val)


from collections import deque
import heapq
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	q = deque([], d)
	h = []
	for i in range(d):
		while len(q) and l[i] >= l[q[-1]]:
			q.pop()
		q.append(i)
	for i in range(i + 1, len(l)):
		heapq.heappush(h, l[q[0]])
		while len(q) and q[0] <= i - d:
			q.popleft()
		while len(q) and l[i] >= l[q[-1]]:
			q.pop()
		q.append(i)
	heapq.heappush(h, l[q[0]])
	print(h[0])


from collections import deque
[n, q] = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
for t0 in range(q):
	d = int(input())
	dq = deque()
	maxc = -1
	for i0 in range(d):
		dq.append(arr[i0])
		maxc = max(maxc, arr[i0])
	maxlist = [maxc]
	for i1 in range(d, n):
		inel = arr[i1]
		dq.append(inel)
		outel = dq.popleft()
		if inel > maxlist[-1]:
			maxlist.append(inel)
		elif outel == maxlist[-1]:
			maxlist.append(max(dq))
	print(min(maxlist))


def min_max(array, sub_length):
	curr_max = max(array[0:sub_length])
	least_max = curr_max
	front = 0
	end = sub_length
	while end < len(array):
		dequeued = array[front]
		enqueued = array[end]
		if dequeued == curr_max:
			curr_max = max(array[front + 1:end + 1])
		elif enqueued > curr_max:
			curr_max = enqueued
		if curr_max < least_max:
			least_max = curr_max
		front += 1
		end += 1
	return least_max
inputs = [int(i) for i in input().strip().split(' ')]
num_queries = inputs[0]
array_length = inputs[1]
array = [int(i) for i in input().strip().split(' ')]
for i in range(num_queries):
	sub_length = int(input().strip())
	print(min_max(array, sub_length))


from collections import deque
from math import sqrt, floor

def go(nums, d):
	q = deque()
	for i in range(d):
		while len(q) > 0 and nums[q[-1]] < nums[i]:
			q.pop()
		q.append(i)
	mx = nums[q[0]]
	for i in range(d, len(nums)):
		while len(q) > 0 and nums[q[-1]] < nums[i]:
			q.pop()
		while len(q) > 0 and q[0] <= i - d:
			q.popleft()
		q.append(i)
		mx = min(mx, nums[q[0]])
	return mx
(n, q) = map(int, input().strip().split(' '))
nums = list(map(int, input().strip().split(' ')))
qs = [int(input()) for i in range(q)]
for d in qs:
	print(go(nums, d))


(n, q) = [int(x) for x in input().split(' ')]
from collections import deque

def running_maxes(arr, d):
	segment = deque()
	for i in range(d):
		segment.append(arr[i])
	current_max = max(segment)
	yield current_max
	i = d
	while i < len(arr):
		removed = segment.popleft()
		added = arr[i]
		i += 1
		segment.append(added)
		if added >= current_max:
			current_max = added
		elif removed == current_max:
			current_max = max(segment)
		yield current_max
arr = list((int(x) for x in input().strip().split(' ')))
for _ in range(q):
	print(min(running_maxes(arr, int(input()))))


import sys

class NotEvenAQueue:

	def __init__(self, size):
		self.data = [-sys.maxsize for _ in range(size)]
		self.size = size
		self.maximum = -sys.maxsize

	def put(self, d, i):
		if self.data[i % self.size] == self.maximum:
			self.data[i % self.size] = -sys.maxsize
			self.maximum = max(self.data)
		self.data[i % self.size] = d
		if d > self.maximum:
			self.maximum = d

	def get_maximum(self):
		return self.maximum
(n, q) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
d = [int(x) for x in [input().strip() for _ in range(q)]]
for offset in d:
	q = NotEvenAQueue(offset)
	m = list()
	for i in range(offset):
		q.put(a[i], i)
	min_m = q.get_maximum()
	for i in range(offset, n):
		q.put(a[i], i)
		if q.get_maximum() < min_m:
			min_m = q.get_maximum()
	print(min_m)


from collections import deque
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	l = deque()
	m = 0
	for i in range(d - 1, -1, -1):
		if m < a[i]:
			m = a[i]
			l.appendleft(i)
	for i in range(d, n):
		if l[0] + d <= i:
			l.popleft()
		while l and a[l[-1]] < a[i]:
			l.pop()
		l.append(i)
		m = min(m, a[l[0]])
	print(m)


def solve(a, q):
	min_ = 10 ** 6
	max_ = -1
	ind = None
	upper = q
	lower = 0
	while upper <= len(a):
		for i in range(lower, upper):
			temp = a[i]
			if temp > max_:
				ind = i + 1
				max_ = temp
		if max_ < min_:
			min_ = max_
		max_ = -1
		upper = ind + q
		lower = ind
	return min_
(n, q) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for __ in range(q):
	query = int(input())
	print(solve(a, query))


(n, q) = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	curr_max = max((A[i] for i in range(d)))
	min_of_maxes = curr_max
	for i in range(1, n - d + 1):
		(a, b) = (A[i - 1], A[i + d - 1])
		if b > curr_max:
			curr_max = b
			if curr_max < min_of_maxes:
				min_of_maxes = curr_max
		elif a == curr_max:
			curr_max = max((A[j] for j in range(i, i + d)))
			if curr_max < min_of_maxes:
				min_of_maxes = curr_max
	print(min_of_maxes)


from collections import deque
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))

def MaxSlidingWindow(A, k):
	D = deque()
	(res, i) = ([], 0)
	for i in range(len(A)):
		while D and D[-1][0] <= A[i]:
			D.pop()
		D.append((A[i], i + k - 1))
		if i >= k - 1:
			res.append(D[0][0])
		if i == D[0][1]:
			D.popleft()
	return min(res)
for _ in range(q):
	query = int(input())
	print(MaxSlidingWindow(a, query))


(n, q) = [int(arr) for arr in input().strip().split()]
data = [int(data) for data in input().strip().split()]
query = []
for i in range(q):
	query.append(int(input()))
for d in query:
	max_index = []
	min_nums = []
	for i in range(n):
		while max_index != [] and data[i] > data[max_index[-1]]:
			max_index.pop()
		max_index.append(i)
		if i >= d - 1:
			min_nums.append(data[max_index[0]])
			if max_index[0] == i + 1 - d:
				max_index.pop(0)
	print(min(min_nums))


(n, q) = map(int, input().split())
sequence = list(map(int, input().split()))

def debug(ds):
	for i in ds:
		print(i, end=' ')
	print()
for _ in range(q):
	d = int(input())
	max_current = max(sequence[0:d])
	min_ans = max_current
	for left in range(1, len(sequence) - d + 1):
		removed = sequence[left - 1]
		added = sequence[left + d - 1]
		if added > max_current:
			max_current = added
		elif removed == max_current:
			max_current = max(sequence[left:left + d])
			if min_ans > max_current:
				min_ans = max_current
		elif max_current >= added:
			pass
	print(min_ans)


from collections import *
(n, q) = list((int(x) for x in input().split(' ')))
a = list((int(x) for x in input().split(' ')))
ds = list((int(input()) for x in range(q)))
for d in ds:
	queue = deque()

	def push_out(new_index):
		if queue and queue[0] <= new_index - d:
			queue.popleft()

	def add_at(index):
		while queue and a[queue[-1]] < a[index]:
			queue.pop()
		queue.append(index)

	def maximum():
		return a[queue[0]]

	def slide(new_index):
		add_at(new_index)
		push_out(new_index)
	for i in range(d):
		add_at(i)
	minimum = max((a[i] for i in range(d)))
	for start in range(0, n - d + 1):
		minimum = min(maximum(), minimum)
		new_index = start + d
		if new_index < n:
			slide(new_index=new_index)
	print(minimum)


import heapq
(n, num_queries) = map(int, input().strip().split())
nums = [int(i) for i in input().strip().split()]
for _ in range(num_queries):
	d = int(input().strip())
	if d >= n:
		print(max(nums))
		continue
	window_max = max(nums[:d])
	moving_min = window_max
	i = 1
	while i + d <= n:
		moved_out = nums[i - 1]
		moved_in = nums[i + d - 1]
		max_moved_out = moved_out == window_max
		new_max_moved_in = moved_in >= window_max
		if new_max_moved_in:
			window_max = moved_in
			moving_min = min(moving_min, window_max)
		elif max_moved_out:
			window_max = max(nums[i:i + d])
			moving_min = min(moving_min, window_max)
		i += 1
	print(moving_min)


def query(n, d, a):
	minimum = maximum = max(a[:d])
	for i in range(1, n - d + 1):
		if maximum <= a[i + d - 1]:
			maximum = a[i + d - 1]
		elif maximum == a[i - 1]:
			maximum = max(a[i:i + d])
			minimum = min(maximum, minimum)
	return minimum
(n, q) = input().split()
(n, q) = (int(n), int(q))
a = list(map(int, input().split()))
for a0 in range(q):
	d = int(input())
	print(query(n, d, a))


from collections import deque
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	mi = float('inf')
	ma = float('-inf')
	for i in range(n):
		if i + d > n:
			break
		if i == 0:
			b = deque(a[0:d])
			ma = max(b)
		else:
			val = b.popleft()
			b.append(a[i + d - 1])
			if ma < b[-1]:
				ma = b[-1]
			elif ma == val:
				ma = max(b)
		mi = min(ma, mi)
	print(mi)


(n, q) = map(int, input().split(' '))
a = [int(x) for x in input().split(' ')]
for _ in range(q):

	def maxSlidingWindow(nums, k):
		from collections import deque

		def en_maxqueue(maxq, n):
			while maxq and maxq[-1] < n:
				maxq.pop()
			maxq.append(n)
		if k == 0:
			return []
		maxq = deque([nums[0]])
		res = []
		mi = 100000000000000
		for i in range(1, k):
			en_maxqueue(maxq, nums[i])
		res.append(maxq[0])
		for i in range(k, len(nums)):
			if nums[i - k] == maxq[0]:
				maxq.popleft()
			en_maxqueue(maxq, nums[i])
			res.append(maxq[0])
		print(min(res))
	d = int(input())
	maxSlidingWindow(a, d)


import copy

def f(A, d):
	deq = []
	maxes = []
	for i in range(len(A)):
		while deq != [] and (A[deq[0]] < A[i] or i - deq[0] >= d):
			deq.pop(0)
		while deq != [] and A[deq[-1]] < A[i]:
			deq.pop()
		deq.append(i)
		if i >= d - 1:
			maxes.append(A[deq[0]])
	return min(maxes)
(n, q) = tuple([int(i) for i in input().split()])
A = [int(i) for i in input().split()]
for i in range(q):
	d = int(input())
	print(f(A, d))


(n, q) = [int(c) for c in input().strip().split(' ')]
alist = [int(c) for c in input().strip().split(' ')]
for _ in range(q):
	d = int(input().strip())
	dq = []
	amin = 10 ** 6 + 1
	for i in range(d):
		while dq and alist[i] > alist[dq[-1]]:
			dq.pop()
		dq.append(i)
	for i in range(d, n):
		amin = min(amin, alist[dq[0]])
		while dq and dq[0] <= i - d:
			dq.pop(0)
		while dq and alist[i] > alist[dq[-1]]:
			dq.pop()
		dq.append(i)
	amin = min(amin, alist[dq[0]])
	print(amin)


import sys
line = sys.stdin.readline().split(' ')
(n, q) = (int(line[0]), int(line[1]))
line = sys.stdin.readline().split(' ')
A = [int(a) for a in line]

def findmax(D, m, n):
	m_val = D[m]
	m_idx = m
	for i in range(m + 1, n):
		if D[i] > m_val:
			m_val = D[i]
			m_idx = i
	return (m_val, m_idx)
for qq in range(q):
	d = int(sys.stdin.readline())
	(maxval, maxidx) = findmax(A, 0, d)
	minmax = maxval
	for i in range(d, n):
		if i - d == maxidx:
			(maxval, maxidx) = findmax(A, maxidx + 1, i + 1)
			minmax = min(maxval, minmax)
		elif A[i] > maxval:
			(maxval, maxidx) = (A[i], i)
			minmax = min(maxval, minmax)
		elif A[i] == maxval:
			maxidx = i
	sys.stdout.write(str(minmax) + '\n')


def max_c(l):
	if not l:
		return None
	m = l[0]
	c = 1
	for i in l[1:]:
		if i > m:
			m = i
			c = 1
		elif i == m:
			c += 1
	return (m, c)

def min_max(n, d, l):
	(m, c) = max_c(l[:d])
	min_max = m
	for i in range(n - d):
		if l[i] == m:
			c -= 1
		newv = l[i + d]
		if c == 0:
			(m, c) = max_c(l[i + 1:i + d + 1])
		elif m == newv:
			c += 1
		elif m < newv:
			m = newv
			c = 1
		min_max = min(min_max, m)
	return min_max
(n, q) = map(int, input().strip().split())
seq = list(map(int, input().strip().split()))
for _ in range(q):
	i = int(input().strip())
	print(min_max(n, i, seq))


import collections

def minimax(A, d):
	n = len(A)
	Q = collections.deque()
	for a in A[:d]:
		while Q and a > Q[-1]:
			Q.pop()
		Q.append(a)
	best = Q[0]
	for i in range(n - d):
		leave = A[i]
		enter = A[i + d] if i + d < n else None
		if Q and leave == Q[0]:
			Q.popleft()
		if enter:
			while Q and enter > Q[-1]:
				Q.pop()
			Q.append(enter)
		if Q[0]:
			best = min(best, Q[0])
	return best
inp = input().strip().split()
(n, q) = (int(inp[0]), int(inp[1]))
A = [int(i) for i in input().strip().split()]
for i in range(q):
	d = int(input().strip())
	print(minimax(A, d))


from collections import deque
(n, q) = map(int, input().strip().split())
arr = [int(s) for s in input().strip().split()]
for _ in range(q):
	d = int(input())
	window = deque(arr[:d])
	mm = m = max(window)
	for x in arr[d:]:
		window.append(x)
		if window.popleft() == m:
			m = max(window)
			mm = min(mm, m)
	print(mm)


from collections import deque
(n, q) = [int(f) for f in input().strip().split(' ')]
arr = [int(f) for f in input().strip().split(' ')]
for i in range(q):
	d = int(input().strip())
	deque_length = d + 1
	maxs = [0] * deque_length
	read = 0
	write = 1
	maxs[0] = arr[0]
	for j in range(1, d):
		v = arr[j]
		while read != write and v > maxs[write - 1]:
			write = (write - 1 + deque_length) % deque_length
		maxs[write] = v
		write = (write + 1) % deque_length
	minn = maxs[read]
	for j in range(d, n):
		v = arr[j]
		while read != write and v > maxs[write - 1]:
			write = (write - 1 + deque_length) % deque_length
		maxs[write] = v
		write = (write + 1) % deque_length
		if arr[j - d] == maxs[read]:
			read = (read + 1) % deque_length
		if maxs[read] < minn:
			minn = maxs[read]
	print(minn)


def build_affected_area(arr):
	left = [0] * len(arr)
	for i in range(1, len(arr)):
		accu = 0
		j = i - 1
		while j >= 0:
			if arr[i] < arr[j]:
				break
			accu += left[j] + 1
			j -= left[j] + 1
		left[i] = accu
	right = [0] * len(arr)
	for i in range(len(arr) - 2, -1, -1):
		accu = 0
		j = i + 1
		while j < len(arr):
			if arr[i] < arr[j]:
				break
			accu += right[j] + 1
			j += right[j] + 1
		right[i] = accu
	return [left[i] + right[i] + 1 for i in range(len(arr))]

def build_reverse_mapping(arr, area):
	mapping = {}
	for i in range(len(arr)):
		if area[i] not in mapping or mapping[area[i]] > arr[i]:
			mapping[area[i]] = arr[i]
	tmp = sorted(list(mapping.items()))
	map_list = [tmp[-1]]
	for i in range(len(tmp) - 2, -1, -1):
		if tmp[i][1] >= map_list[-1][1]:
			continue
		map_list.append(tmp[i])
	map_list.reverse()
	return map_list

def find_from_mapping(mapping, d):

	def binary_search(start, end, d):
		if start == end:
			return mapping[start][1]
		mid = (start + end) // 2
		if mapping[mid][0] >= d:
			return binary_search(start, mid, d)
		else:
			return binary_search(mid + 1, end, d)
	return binary_search(0, len(mapping) - 1, d)
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
area = build_affected_area(arr[:n])
mapping = build_reverse_mapping(arr, area)
for _ in range(q):
	d = int(input())
	print(find_from_mapping(mapping, d))


(n, q) = map(int, input().strip().split(' '))
arr = list(map(int, input().strip().split(' ')))
for _ in range(q):
	d = int(input().strip())
	i = 1
	tempMax = max(arr[i - 1:d])
	minm = tempMax
	while i < len(arr) - d:
		skipped = arr[i]
		added = arr[i + d]
		if added >= tempMax:
			tempMax = added
		elif skipped == tempMax:
			tempMax = max(arr[i + 1:i + d + 1])
			minm = min(minm, tempMax)
		i += 1
	print(minm)


from collections import deque

def solve(A, d):
	queue = deque()
	for (i, a) in enumerate(A[:d]):
		while queue and A[queue[-1]] <= a:
			queue.pop()
		queue.append(i)
	best = A[queue[0]]
	for (i, a) in enumerate(A[d:], d):
		if queue[0] <= i - d:
			queue.popleft()
		while queue and A[queue[-1]] <= a:
			queue.pop()
		queue.append(i)
		best = min(best, A[queue[0]])
	return best
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	print(solve(A, d))


(n, q) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
for _ in range(q):
	d = int(input().strip())
	max_val = max(a[:d])
	min_val = max_val
	for i in range(1, n - d + 1):
		if max_val == a[i - 1]:
			max_val = max(a[i:i + d])
		elif a[i + d - 1] > max_val:
			max_val = a[i + d - 1]
		if max_val < min_val:
			min_val = max_val
	print(min_val)


import heapq
(n, q) = list(map(int, input().strip().split(' ')))
a = list(map(int, input().strip().split(' ')))
b = [[-a[i], False] for i in range(n)]
for _ in range(q):
	d = int(input())
	for i in range(d):
		b[i][1] = True
	h = b[:d]
	heapq.heapify(h)
	res = -10 ** 6
	for i in range(n - d + 1):
		while not h[0][1]:
			heapq.heappop(h)
		res = max(res, h[0][0])
		if i + d < n:
			b[i][1] = False
			b[i + d][1] = True
			heapq.heappush(h, b[i + d])
	for i in range(n - d, n):
		b[i][1] = False
	print(-res)


import sys
from collections import deque
(n, q) = [int(x) for x in input().strip().split(' ')]
A = [int(a) for a in input().strip().split(' ')]
D = [int(input().strip()) for _ in range(q)]

def max_indexed(iter):
	return max(enumerate(iter), key=lambda x: x[1])
for d in D:
	min_q = sys.maxsize
	q = deque(A[:d], maxlen=d)
	max_q = max_indexed(q)
	max_q = (max_q[0] - d, max_q[1])
	for (ia, a) in enumerate(A[d:]):
		min_q = min(min_q, max_q[1])
		q.append(a)
		if ia - max_q[0] == d:
			max_q = max_indexed(q)
			max_q = (max_q[0] - d + 1 + ia, max_q[1])
		elif a > max_q[1]:
			max_q = (ia, a)
	else:
		min_q = min(min_q, max_q[1])
	print(min_q)


from collections import deque
(element_count, query_count) = [int(x) for x in input().split()]
elements = [int(x) for x in input().split()]
for _ in range(query_count):
	width = int(input())
	window = deque(elements[:width])
	window_max = max(window)
	minimum = window_max
	for i in range(width, element_count):
		popped = window.popleft()
		window.append(elements[i])
		if popped == window_max or window[-1] > window_max:
			window_max = max(window)
			if window_max < minimum:
				minimum = window_max
	print(minimum)


from math import inf
from collections import deque

class MaxQueue:

	def __init__(self, d):
		self.d = d
		self.max = -inf
		self.queue = deque()

	def push(self, v):
		if len(self.queue) < self.d:
			self.queue.append(v)
			self.max = max(self.max, v)
		else:
			old = self.queue.popleft()
			self.queue.append(v)
			if old != self.max:
				self.max = max(self.max, v)
			elif old <= v:
				self.max = v
			else:
				self.max = max(self.queue)

	def get_max(self):
		return self.max

	def is_full(self):
		return len(self.queue) == self.d

def solution(A, d):
	q = MaxQueue(d)
	for i in range(d - 1):
		q.push(A[i])
	maxs = []
	for a in A[d - 1:]:
		q.push(a)
		maxs.append(q.get_max())
	return min(maxs)

def main():
	(N, Q) = map(int, input().strip().split())
	A = list(map(int, input().strip().split()))
	D = [int(input().strip()) for _ in range(Q)]
	for d in D:
		print(solution(A, d))
main()


import heapq
(n, q) = list(map(int, input().split(' ')))
arr = list(map(int, input().split(' ')))
memo = {}

def find_min(d):
	if d in memo:
		return memo[d]
	h = []
	for i in range(0, d - 1):
		heapq.heappush(h, (-arr[i], i))
	possible = []
	for start in range(0, n - d + 1):
		end = start + d - 1
		heapq.heappush(h, (-arr[end], end))
		while h[0][1] < start:
			heapq.heappop(h)
		possible.append(-h[0][0])
	memo[d] = min(possible)
	return memo[d]
for _ in range(q):
	d = int(input())
	print(find_min(d))


import collections
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
for _ in range(q):
	d = int(input())
	queue = collections.deque()
	m = float('inf')
	for (i, num) in enumerate(A):
		while queue and A[queue[-1]] < num:
			queue.pop()
		queue.append(i)
		if queue[0] == i - d:
			queue.popleft()
		if i >= d - 1:
			if A[queue[0]] < m:
				m = A[queue[0]]
	print(m)


(n, q) = [int(number) for number in input().split()]
mylist = [int(number) for number in input().split()]
for step in range(q):
	minmax = 0
	d = int(input())
	maxnumber = 0
	for i in range(n):
		if mylist[i] >= maxnumber:
			maxnumber = mylist[i]
		elif i >= d:
			if mylist[i - d] == maxnumber:
				maxnumber = max(mylist[i - d + 1:i + 1])
		if i >= d - 1:
			if minmax == 0 or minmax > maxnumber:
				minmax = maxnumber
	print(minmax)


stin = lambda : tuple(map(int, input().strip().split()))
(n, q) = stin()
lst = stin()

def nearest_largers():
	lfts = [-1] * n
	rgts = [n] * n
	st = list()
	for (i, a) in enumerate(lst):
		while st and lst[st[-1]] < a:
			rgts[st.pop()] = i
		if st:
			if lst[st[-1]] > a:
				lfts[i] = st[-1]
			else:
				lfts[i] = lfts[st[-1]]
		st.append(i)
	return (lfts, rgts)

def max_widths():
	lrs = nearest_largers()
	return list((r - l - 1 for (l, r) in zip(*lrs)))

def mins_of_sliding_maxs():
	res = [float('inf')] * (n + 1)
	for (a, width) in zip(lst, max_widths()):
		res[width] = min(res[width], a)
	for width in range(n - 1, 0, -1):
		res[width] = min(res[width], res[width + 1])
	return res
mins = mins_of_sliding_maxs()
for _ in range(q):
	print(mins[int(input())])


import sys
from collections import deque

def query(lst, d, n):
	if d == 1:
		return min(lst)
	if d == n:
		return max(lst)
	currentmax = -1
	queue = deque()
	for i in range(d):
		queue.append(lst[i])
	currentmax = max(queue)
	globalmin = currentmax
	for i in range(d, n, 1):
		if lst[i] > currentmax:
			currentmax = lst[i]
			queue.popleft()
			queue.append(lst[i])
		elif currentmax == queue[0]:
			queue.popleft()
			queue.append(lst[i])
			currentmax = max(queue)
		else:
			queue.popleft()
			queue.append(lst[i])
		globalmin = min(globalmin, currentmax)
	return globalmin
(n, q) = [int(i) for i in input().split()]
lst = [int(i) for i in input().split()]
for i in range(q):
	d = int(input())
	print(query(lst, d, n))


import collections
q = int(input().split()[1])
A = list(map(int, input().split()))
amax = max(A)
for query in range(q):
	d = int(input().strip())
	minmax = amax
	iq = collections.deque()
	for i in range(d):
		try:
			while A[iq[-1]] <= A[i]:
				iq.pop()
		except IndexError:
			pass
		iq.append(i)
	for i in range(d, len(A)):
		minmax = min(minmax, A[iq[0]])
		if i == iq[0] + d:
			iq.popleft()
		try:
			while A[iq[-1]] <= A[i]:
				ipop = iq.pop()
		except IndexError:
			pass
		iq.append(i)
	minmax = min(minmax, A[iq[0]])
	print(minmax)


from collections import deque
(n, q) = map(int, input().split())
queue = deque(map(int, input().split()))
for _ in range(q):
	d = int(input())
	little_queue = deque([])
	max_ = 0
	for _ in range(d):
		num = queue.popleft()
		little_queue.append(num)
		if num > max_:
			max_ = num
		queue.append(num)
	min_ = max_
	for _ in range(n - d):
		num = queue.popleft()
		old_num = little_queue.popleft()
		little_queue.append(num)
		queue.append(num)
		if num >= max_:
			max_ = num
		elif old_num == max_:
			max_ = max(little_queue)
		if max_ < min_:
			min_ = max_
	print(min_)


from collections import deque

def add_useful(qi, a, i):
	if i >= len(a):
		return
	while qi and a[i] > a[qi[0]]:
		qi.popleft()
	qi.appendleft(i)

def drain_outsiders(qi, i, k):
	while qi and qi[-1] <= i - k:
		qi.pop()

def get_min(my_min, last_max):
	if my_min == None:
		my_min = last_max
	elif my_min > last_max:
		my_min = last_max
	return my_min

def get_min_max(a, k):
	my_min = None
	qi = deque()
	for i in range(0, k):
		add_useful(qi, a, i)
	for i in range(k, len(a) + 1):
		last_max = a[qi[-1]]
		my_min = get_min(my_min, last_max)
		drain_outsiders(qi, i, k)
		add_useful(qi, a, i)
	return my_min
window = list()
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
for _ in range(m):
	k = int(input())
	print(get_min_max(a, k))


(N, Q) = map(int, input().split())
A = list(map(int, input().split()))
D = []
for q in range(Q):
	d = int(input())
	min_num = 10 ** 6 + 1
	i = 0
	max_idx = -1
	while i <= N - d:
		if i > max_idx:
			max_num = -1
			for j in range(i, i + d):
				if A[j] >= max_num:
					max_num = A[j]
					max_idx = j
		if max_num < min_num:
			min_num = max_num
		i += 1
	print(min_num)


import sys
from heapq import *
import math

def solve(a, d):
	n = len(a)
	h = list(zip([-x for x in a[:d]], range(d)))
	heapify(h)
	result = -h[0][0]
	for i in range(d, n):
		while len(h) >= d and i - h[0][1] >= d:
			heappop(h)
		heappush(h, (-a[i], i))
		if -h[0][0] < result:
			result = -h[0][0]
	return result
[n, q] = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
for i in range(q):
	d = int(input().strip())
	print(solve(a, d))


from queue import deque
(N, Q) = map(int, input().strip().split(' '))
A = [int(n) for n in input().strip().split(' ')]
for _ in range(Q):
	d = int(input().strip())
	q = deque(A[:d])
	local_max = max(q)
	global_min = local_max
	for i in range(d, N):
		val = A[i]
		out = q.popleft()
		q.append(val)
		if val > local_max:
			local_max = val
			if local_max < global_min:
				global_min = local_max
		elif out == local_max:
			local_max = max(q)
			if local_max < global_min:
				global_min = local_max
	print(global_min)


def naive_solve(arr, d):
	return min((max(arr[i:i + d]) for i in range(len(arr) - d + 1)))

def max_last(start, stop, arr):
	i = start
	for j in range(start, stop):
		if arr[j] >= arr[i]:
			i = j
	return i

def naive_solve2(arr, d):
	imax = max_last(0, d, arr)
	res = arr[imax]
	for i in range(1, len(arr) - d + 1):
		if imax < i:
			imax = max_last(i, i + d, arr)
		else:
			imax = imax if arr[imax] > arr[i + d - 1] else i + d - 1
		res = min(res, arr[imax])
	return res
parse = lambda : [int(x) for x in input().split()]
(n, q) = parse()
arr = parse()
for _ in range(q):
	d = int(input())
	print(naive_solve2(arr, d))


def decr_queue_append(max_queue, elem, i):
	while max_queue and max_queue[-1][0] < elem:
		max_queue.pop()
	max_queue.append((elem, i))
(n, q) = input().strip().split(' ')
(n, q) = (int(n), int(q))
a = list(map(int, input().strip().split(' ')))
for _ in range(q):
	Min = 1000000
	d = int(input())
	max_queue = []
	for i in range(d - 1):
		decr_queue_append(max_queue, a[i], i)
	for i in range(n - d + 1):
		decr_queue_append(max_queue, a[i + d - 1], i + d - 1)
		if max_queue[0][1] < i:
			max_queue.pop(0)
		Min = min(Min, max_queue[0][0])
	print(Min)


from collections import deque
from math import sqrt, floor

def go(nums, d):
	q = deque()
	for i in range(d):
		while len(q) > 0 and nums[q[-1]] < nums[i]:
			q.pop()
		q.append(i)
	mx = nums[q[0]]
	for i in range(d, len(nums)):
		while len(q) > 0 and nums[q[-1]] < nums[i]:
			q.pop()
		while len(q) > 0 and q[0] <= i - d:
			q.popleft()
		q.append(i)
		mx = min(mx, nums[q[0]])
	return mx
(n, q) = map(int, input().strip().split(' '))
nums = list(map(int, input().strip().split(' ')))
qs = [int(input()) for i in range(q)]
for d in qs:
	print(go(nums, d))


from collections import deque

def fun(arr, d):
	window = deque([arr.pop() for _ in range(d)], maxlen=d)
	minmax = max(window)
	curmax = minmax
	while arr:
		rmval = window.popleft()
		window.append(arr.pop())
		if curmax == rmval:
			curmax = max(window)
		else:
			curmax = max(curmax, window[-1])
		minmax = min(minmax, curmax)
	return minmax
(n, q) = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
for _ in range(q):
	d = int(input())
	print(fun(arr[:], d))


import sys
import math

def resolve_query(a, q, n):
	min_ = math.inf
	start = 0
	while start <= n - q:
		max_ = (start, a[start])
		for i in range(start + 1, start + q):
			if a[i] > max_[1]:
				max_ = (i, a[i])
		if min_ > max_[1]:
			min_ = max_[1]
		start = max_[0] + 1
	return min_
(n, x) = list(map(int, input().strip().split(' ')))
a = list(map(int, input().strip().split(' ')))
for i in range(x):
	print(resolve_query(a, int(input()), n))


import sys
import queue

def getMax(q, d):
	currentMax = -float('inf')
	for i in range(d):
		val = q.get()
		if val > currentMax:
			currentMax = val
		q.put(val)
	return currentMax

def processQuery(d, arr):
	minVal = float('inf')
	startIndex = 0
	while startIndex < len(arr) - d + 1:
		maxy = max(arr[startIndex:startIndex + d])
		minVal = min(minVal, maxy)
		val = arr[startIndex]
		startIndex += 1
		if val != maxy:
			while arr[startIndex] != maxy:
				startIndex += 1
	print(minVal)
(n, m) = input().strip().split(' ')
(n, m) = [int(n), int(m)]
arr = input().strip().split(' ')
arr = list(map(lambda x: int(x), arr))
for i in range(m):
	query = int(input().strip())
	processQuery(query, arr)


import sys
(num, n) = map(int, input().split(' '))
lst = list(map(int, input().strip(' ').split()))
for i in range(n):
	x = int(input())
	temp = 0
	count = 0
	i = 0
	minimum = 0
	while i < num - x + 1:
		temp = 0
		for j in range(i, x + i):
			if lst[j] > temp:
				temp = lst[j]
				pos = j
		if i == 0:
			minimum = temp
		elif temp < minimum:
			minimum = temp
		i = pos + 1
	print(minimum)


from collections import deque

def min_query(d, a):
	max_r = 0
	b = deque()
	for i in range(d):
		while b and a[i] > b[-1][1]:
			b.pop()
		b.append((i, a[i]))
	min_q = b[0][1]
	for i in range(d, len(a)):
		if b[0][0] == i - d:
			b.popleft()
		while b and a[i] > b[-1][1]:
			b.pop()
		b.append((i, a[i]))
		min_q = min(b[0][1], min_q)
	return min_q
(n, q) = (int(x) for x in input().strip().split(' '))
a = [int(x) for x in input().strip().split(' ')]
for _ in range(q):
	d = int(input())
	print(min_query(d, a))


def minmax(sequence, d):
	maxlist = []
	start = 0
	end = d
	if d == 1:
		return min(sequence)
	if d == len(sequence):
		return max(sequence)
	submax = max(sequence[start:end])
	maxlist.append(submax)
	for _ in range(1, len(sequence) + 1 - d):
		start = start + 1
		end = end + 1
		if sequence[start - 1] == submax:
			submax = max(sequence[start:end])
		elif sequence[end - 1] > submax:
			submax = sequence[end - 1]
		maxlist.append(submax)
	return min(maxlist)
(n, q) = input().strip().split(' ')
n = int(n)
q = int(q)
sequence = list(map(int, input().strip().split(' ')))
for _ in range(q):
	d = int(input().strip())
	print(minmax(sequence, d))


def minmax(sequence, d):
	maxlist = []
	start = 0
	end = d
	if d == 1:
		return min(sequence)
	if d == len(sequence):
		return max(sequence)
	submax = max(sequence[start:end])
	maxlist.append(submax)
	for _ in range(1, len(sequence) + 1 - d):
		start = start + 1
		end = end + 1
		if sequence[start - 1] == submax:
			submax = max(sequence[start:end])
		elif sequence[end - 1] > submax:
			submax = sequence[end - 1]
		maxlist.append(submax)
	return min(maxlist)
(n, q) = input().strip().split(' ')
n = int(n)
q = int(q)
sequence = list(map(int, input().strip().split(' ')))
for _ in range(q):
	d = int(input().strip())
	print(minmax(sequence, d))


from collections import deque
(n, q) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
for _ in range(q):
	d = int(input())
	M = -1
	a = deque()
	if d == 1:
		print(min(A))
		continue
	if d == n:
		print(max(A))
		continue
	for i in range(d):
		a.append(A[i])
		M = A[i] if A[i] > M else M
	m = M
	for i in range(d, n):
		a.append(A[i])
		if a.popleft() == M:
			M = max(a)
		else:
			M = a[-1] if M < a[-1] else M
		m = M if m > M else m
	print(m)


def minOfMax(arr, d):
	if len(arr) == 0:
		return 10 ** 5
	elif d == 1:
		return min(arr)
	else:
		M = max(arr)
		idx = arr.index(M)
		if idx < d and len(arr) - idx - 1 < d:
			return M
		elif idx < d:
			return min(M, minOfMax(arr[idx + 1:], d))
		elif len(arr) - idx - 1 < d:
			return min(M, minOfMax(arr[:idx], d))
		else:
			return min(M, minOfMax(arr[:idx], d), minOfMax(arr[idx + 1:], d))
(n, q) = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
for _ in range(q):
	d = int(input().strip())
	print(minOfMax(A, d))


(n, q) = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
for i in range(q):
	a = int(input())
	b = arr[:a]
	maxi = max(b)
	large = maxi
	mini = maxi
	front = 0
	size = a
	for j in range(a, n):
		avail = (front + a) % a
		deq = b[front]
		b[avail] = arr[j]
		if deq == large:
			large = max(b)
			mini = min(mini, large)
		else:
			large = max(large, arr[j])
			mini = min(mini, large)
		front = (front + 1) % a
	b = []
	print(mini)


from collections import deque

def solve(numbers, d):
	q = deque()
	max_q = deque()
	min_a = float('inf')
	for i in range(len(numbers)):
		y = numbers[i]
		q.append(y)
		if len(q) > d:
			x = q.popleft()
			if x == max_q[0]:
				max_q.popleft()
		if len(max_q) == 0 or y <= max_q[-1]:
			max_q.append(y)
		else:
			while len(max_q) > 0 and max_q[-1] < y:
				max_q.pop()
			max_q.append(y)
		if len(q) == d and min_a > max_q[0]:
			min_a = max_q[0]
	return min_a
(q, n) = map(int, input().strip().split())
numbers = list(map(int, input().strip().split()))
for _ in range(q):
	d = int(input())
	res = solve(numbers, d)
	print(res)


import sys
from collections import deque

def solve(n, A, d):
	if n == d:
		return max(A)
	last = d - 1
	local_max = max(A[:d])
	ans = local_max
	while last < n - 1:
		last += 1
		local_max = max

def printMax(arr, n, k):
	ans = []
	Qi = deque()
	for i in range(k):
		while Qi and arr[i] >= arr[Qi[-1]]:
			Qi.pop()
		Qi.append(i)
	for i in range(k, n):
		ans.append(arr[Qi[0]])
		while Qi and Qi[0] <= i - k:
			Qi.popleft()
		while Qi and arr[i] >= arr[Qi[-1]]:
			Qi.pop()
		Qi.append(i)
	ans.append(arr[Qi[0]])
	return min(ans)
(n, q) = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for _ in range(q):
	d = int(input())
	print(printMax(A, n, d))


(n, q) = input().split()
(n, q) = [int(n), int(q)]
l = list(map(int, input().split()))
for q_i in range(q):
	d = int(input())
	temp = []
	ma = max(l[:d])
	temp.append(ma)
	for i in range(1, len(l) - d + 1):
		if l[i - 1] == ma:
			ma = max(l[i:i + d])
			temp.append(ma)
		elif l[i + d - 1] >= ma:
			ma = l[i + d - 1]
			temp.append(ma)
	m = min(temp)
	print(m)


(n, q) = [int(x) for x in input().strip().split()]
arr = [int(x) for x in input().strip().split()]
for _ in range(q):
	d = int(input().strip())
	maxes = []
	was_first = False
	for i in range(n - d + 1):
		if i == 0 or was_first == True:
			maxes.append(max(arr[i:i + d]))
		else:
			maxes.append(max(maxes[-1], arr[i + d - 1]))
		if maxes[-1] == arr[i]:
			was_first = True
		else:
			was_first = False
	print(min(maxes))


from collections import deque

def Main():
	(n, q) = map(int, input().strip().split(' '))
	arr = list(map(int, input().strip().split(' ')))
	for i in range(q):
		d = int(input().strip())
		print(get_min(arr, d))

def get_min(arr, d):
	cur_min = float('inf')
	deq = deque([], d)
	for i in range(0, d):
		prune_candidate_maxes(deq, arr, i)
		deq.append(i)
	for i in range(d - 1, len(arr)):
		if not max_in_window(deq, i, d):
			deq.popleft()
		prune_candidate_maxes(deq, arr, i)
		deq.append(i)
		cur_min = arr[deq[0]] if arr[deq[0]] < cur_min else cur_min
	return cur_min

def max_in_window(deq, i, d):
	return deq[0] > i - d

def prune_candidate_maxes(deq, arr, i):
	while len(deq) > 0 and arr[deq[-1]] <= arr[i]:
		deq.pop()

def print_arr_and_deq(arr, deq):
	print(arr)
	ret = '['
	for i in deq:
		ret += str(arr[i])
		ret += ', '
	ret += ']'
	print(ret)
Main()


(n, q) = input().strip().split(' ')
(n, q) = [int(n), int(q)]
a = list(map(int, input().strip().split(' ')))

def findMax(arr):
	val = arr[0]
	idx = 0
	for i in range(len(arr)):
		if val < arr[i]:
			val = arr[i]
			idx = i
	return (val, idx)
for q0 in range(q):
	d = int(input())
	if d == 1:
		print(min(a))
	else:
		minVal = 1000000.0 + 1
		i = 0
		while i <= len(a) - d:
			if i + d > len(a):
				end = len(a)
			else:
				end = i + d
			(val, idx) = findMax(a[i:end])
			idx += i
			if val < minVal:
				minVal = val
			i = idx + 1
		print(minVal)


import sys

def find_min(d, A):
	max_val = 0
	for i in range(d):
		max_val = max(max_val, A[i])
	min_of_max = max_val
	for i in range(d, len(A)):
		if A[i] > max_val:
			max_val = max(max_val, A[i])
		elif A[i - d] == max_val:
			max_val = max(A[i - d + 1:i + 1])
		if max_val < min_of_max:
			min_of_max = max_val
	return min_of_max

def exec_input(fd=sys.stdin):
	(m, n) = map(int, fd.readline().strip().split(' '))
	A = [int(i) for i in fd.readline().strip().split(' ')]
	for a0 in range(n):
		d = int(fd.readline().strip())
		print(find_min(d, A))
exec_input()


from collections import deque
(n, q) = map(int, input().split())
values = list(map(int, input().split()))
for _ in range(q):
	queue = deque()
	d = int(input())
	groupings = n - d + 1
	out_of_group = n - d
	min_group = 1000000
	max = 0
	for i in range(d):
		val = values[i]
		if val > max:
			max = val
		queue.append(values[i])
	if max < min_group:
		min_group = max
	for g in range(d, n):
		val = values[g]
		out = queue.popleft()
		queue.append(val)
		if val > max:
			max = val
		if out >= max:
			max = 0
			for i in queue:
				if i > max:
					max = i
		if max < min_group:
			min_group = max
	print(min_group)


def calMax(l, s, len):
	m = l[s]
	for i in range(s + 1, s + len):
		m = (m, l[i])[l[i] > m]
	return m
[n, q] = list(map(int, input().rstrip().split()))
nu = list(map(int, input().rstrip().split()))
for i in range(q):
	d = int(input())
	max = calMax(nu, 0, d)
	min = max
	mc = 1
	for j in range(d, n):
		en = nu[j]
		ex = nu[j - d]
		if en > max:
			max = en
			mc = 1
		elif en == max:
			mc += 1
		if ex == max:
			mc -= 1
			if not mc:
				max = calMax(nu, j - d + 1, d)
				if max < min:
					min = max
				mc = 1
	print(min)


(n, q) = map(int, input().strip().split(' '))
a = list(map(int, input().strip().split(' ')))
for _ in range(q):
	d = int(input().strip())
	maxs = max(a[0:d])
	res = maxs
	for i in range(1, n - d + 1):
		if maxs == a[i - 1]:
			maxi = max(a[i:i + d])
		else:
			maxi = max(maxs, a[i + d - 1])
		maxs = maxi
		if maxi < res:
			res = maxi
	print(res)


(n, m) = map(int, input().split(' '))
numbers = list(map(int, input().split(' ')))
for _ in range(m):
	q = int(input())
	comparing_i = 0
	answer = max(numbers[:q])
	cur_max = answer
	for n in range(q, len(numbers)):
		if numbers[n] > cur_max:
			cur_max = numbers[n]
		temp = numbers[comparing_i]
		comparing_i += 1
		if temp == cur_max and temp > numbers[n]:
			cur_max = max(numbers[comparing_i:n + 1])
		answer = min(answer, cur_max)
	print(answer)


(_, Q) = map(int, input().split())
values = list(map(int, input().split()))
for _ in range(Q):
	d = int(input())
	cmin = cmax = max((values[i] for i in range(d)))
	for i in range(d, len(values)):
		if values[i - d] == cmax:
			cmax = max((values[i] for i in range(i - d + 1, i + 1)))
		else:
			cmax = max(cmax, values[i])
		cmin = min(cmin, cmax)
	print(cmin)


nq = input().split()
n = int(nq[0])
q = int(nq[1])
arr = list(map(int, input().rstrip().split()))
queries = []
for _ in range(q):
	queries_item = int(input())
	queries.append(queries_item)
i = 0
while i < len(queries):
	d = queries[i]
	max_ele = max(arr[0:d])
	current_min = max_ele
	if d == 1:
		current_min = min(arr)
	elif d == len(arr):
		current_min = max(arr)
	else:
		j = d
		front = 1
		while j < len(arr):
			if max_ele == arr[front - 1]:
				max_ele = max(arr[front:j + 1])
				if current_min > max_ele:
					current_min = max_ele
			elif arr[j] > max_ele:
				max_ele = arr[j]
			j += 1
			front += 1
	print(current_min)
	i += 1


(n, q) = map(int, input().split())
A = [int(_) for _ in input().split()]
for _ in range(q):
	d = int(input())
	current_max = max(A[:d])
	current_min = current_max
	for i in range(1, n - d + 1):
		if A[i - 1] == current_max:
			if A[i + d - 1] != current_max:
				current_max = max(A[i:i + d])
		current_min = min(current_min, current_max)
	print(current_min)


str = input()
li = str.split()
n = int(li[0])
q = int(li[1])
str = input()
arr = str.split()
for i in range(n):
	arr[i] = int(arr[i])
li = []
for i in range(q):
	li.append(int(input()))
mx = -4
for i in range(q):
	d = li[i]
	j = d
	mx = max(arr[:j])
	mn = mx
	while j < n:
		if mx <= arr[j]:
			mx = arr[j]
			if mx < mn:
				mn = mx
		else:
			if mx == arr[j - d]:
				mx = max(arr[j - d + 1:j + 1])
			if mx < mn:
				mn = mx
		j += 1
	print(mn)


from heapq import heappop, heappush, heapify

def minmax(nums, d):
	heap = nums[:d]
	removed = []
	heapify(heap)
	res = heap[0]
	for i in range(d, len(nums)):
		heappush(heap, nums[i])
		heappush(removed, nums[i - d])
		while heap and removed and (heap[0] == removed[0]):
			heappop(heap)
			heappop(removed)
		if heap[0] > res:
			res = heap[0]
	return -res
(n, q) = map(int, input().split())
nums = [-int(x) for x in input().split()]
for _ in range(q):
	d = int(input())
	print(minmax(nums, d))


str = input()
li = str.split()
n = int(li[0])
q = int(li[1])
str = input()
arr = str.split()
for i in range(n):
	arr[i] = int(arr[i])
li = []
for i in range(q):
	li.append(int(input()))
mx = -4
for i in range(q):
	d = li[i]
	j = d
	mx = max(arr[:j])
	mn = mx
	while j < n:
		if mx <= arr[j]:
			mx = arr[j]
			if mx < mn:
				mn = mx
		else:
			if mx == arr[j - d]:
				mx = max(arr[j - d + 1:j + 1])
			if mx < mn:
				mn = mx
		j += 1
	print(mn)


import math
(n, q) = map(int, input().split())
lst = list(map(int, input().split()))
ans = [-1 for i in range(n)]
for _ in range(q):
	d = int(input())
	if ans[d - 1] != -1:
		print(ans[d - 1])
	else:
		min1 = 10 ** 6 + 1
		lastmax = 0
		for i in range(0, d):
			if lst[i] >= lst[lastmax]:
				lastmax = i
		if min1 > lst[lastmax]:
			min1 = lst[lastmax]
		for i in range(1, n - d + 1):
			if lastmax == i - 1:
				lastmax = i
				for j in range(i, i + d):
					if lst[j] >= lst[lastmax]:
						lastmax = j
			elif lst[i + d - 1] >= lst[lastmax]:
				lastmax = i + d - 1
			if min1 > lst[lastmax]:
				min1 = lst[lastmax]
		ans[d - 1] = min1
		print(min1)


def Sol(a, d):
	if d == len(a):
		return max(a)
	maxqueue = [0]
	for k in range(1, d):
		while maxqueue and a[k] > a[maxqueue[-1]]:
			maxqueue.pop()
		maxqueue.append(k)
	res = a[maxqueue[0]]
	for k in range(d, len(a)):
		if k - maxqueue[0] >= d:
			maxqueue.pop(0)
		while maxqueue and a[k] > a[maxqueue[-1]]:
			maxqueue.pop()
		maxqueue.append(k)
		res = min(res, a[maxqueue[0]])
	return res
(N, Q) = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(Q):
	d = int(input())
	print(Sol(a, d))


from collections import deque

def search(l, k):
	d = deque()
	for i in range(k):
		while d and l[i] > l[d[-1]]:
			d.pop()
		d.append(i)
	min = l[d[0]]
	for i in range(k, n):
		if min > l[d[0]]:
			min = l[d[0]]
		while d and d[0] <= i - k:
			d.popleft()
		while d and l[i] > l[d[-1]]:
			d.pop()
		d.append(i)
	if min > l[d[0]]:
		min = l[d[0]]
	return min
(n, m) = map(int, input().split())
l = list(map(int, input().split()))
for _ in range(m):
	z = search(l, int(input()))
	print(z)


import sys, heapq
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
assert n == len(a)
import heapq
for _ in range(q):
	d = int(input())
	q = [(-a[i], i) for i in range(d - 1)]
	heapq.heapify(q)
	minmax = 10 ** 6
	for i in range(n - d + 1):
		heapq.heappush(q, (-a[i + d - 1], i + d - 1))
		while q[0][1] < i:
			heapq.heappop(q)
		maxi = -q[0][0]
		minmax = min(minmax, -q[0][0])
	print(minmax)