Это упрощенная версия задачи, в этой версии \(1 \le n, m \le 100\). Вы можете взламывать эту задачу, только если вы заблокировали обе версии.
Пусть задана последовательность целых чисел \(a=[a_1,a_2,\dots,a_n]\) длины \(n\). Её подпоследовательностью называется любая такая, которая получена удалением нуля или более элементов из последовательности \(a\) (они не обязательно идут подряд). Например, для последовательности \(a=[11,20,11,33,11,20,11]\):
- \([11,20,11,33,11,20,11]\), \([11,20,11,33,11,20]\), \([11,11,11,11]\), \([20]\), \([33,20]\) — подпоследовательности (некоторые из большого списка);
- \([40]\), \([33,33]\), \([33,20,20]\), \([20,20,11,11]\) — не являются подпоследовательностями.
Пусть дополнительно задано целое неотрицательное число \(k\) (\(1 \le k \le n\)), тогда подпоследовательность называется оптимальной, если:
- она имеет длину \(k\) и сумма её элементов максимальная возможная среди всех подпоследовательностей длины \(k\);
- и среди всех подпоследовательностей длины \(k\), которые удовлетворяют предыдущему пункту она лексикографически минимальна.
Напомним, что последовательность \(b=[b_1, b_2, \dots, b_k]\) лексикографически меньше последовательности \(c=[c_1, c_2, \dots, c_k]\), если первый слева элемент в котором они различаются меньше в последовательности \(b\) чем в \(c\). Формально: существует такое \(t\) (\(1 \le t \le k\)), что \(b_1=c_1\), \(b_2=c_2\), ..., \(b_{t-1}=c_{t-1}\) и одновременно \(b_t<c_t\). Например:
- \([10, 20, 20]\) лексикографически меньше чем \([10, 21, 1]\),
- \([7, 99, 99]\) лексикографически меньше чем \([10, 21, 1]\),
- \([10, 21, 0]\) лексикографически меньше чем \([10, 21, 1]\).
Вам задана последовательность \(a=[a_1,a_2,\dots,a_n]\) и \(m\) запросов, каждый состоит из двух чисел \(k_j\) и \(pos_j\) (\(1 \le k \le n\), \(1 \le pos_j \le k_j\)). Для каждого запроса выведите значение, которое стоит в индексе \(pos_j\) оптимальной подпоследовательности заданной последовательности \(a\) для \(k=k_j\).
Например, если \(n=4\), \(a=[10,20,30,20]\), \(k_j=2\), тогда оптимальная подпоследовательность равна \([20,30]\) — она минимальная лексикографически среди всех подпоследовательностей длины \(2\) с максимальной суммой элементов. Таким образом, ответом на запрос вида \(k_j=2\), \(pos_j=1\) будет число \(20\), а ответом на запрос вида \(k_j=2\), \(pos_j=2\) будет число \(30\).