Задача №113873. Настя и CodeCoder
Настя и ее одноклассники часто пишут соревнования на платформе CodeCoder. Сейчас Насте захотелось повести аналитику этих соревнований. Она пронумеровала одноклассников и для каждого раунда записала номер одноклассника, который написал этот раунд лучше всех. (оказалось, что для каждого раунда нашелся такой одноклассник). Все жители Байтландии знают, что число k - волшебное, поэтому Настя решила, что если кто-то из ее одноклассников написал лучше всех ровно k раундов, то этот одноклассник тоже волшебный. Теперь ей стало интересно узнать для некоторых подотрезков из списка раундов узнать, найдется ли волшебный одноклассник, если рассматривать только раунды на этом подотрезке, и, если найдется, то привести пример. Сейчас Настя готовится к математической олимпиаде Байтландии, поэтому попросила вас помочь ей. Так как она хочет получить результат как можно быстрее, то ее устроит номер любого одноклассника, являющегося волшебным на подотрезке раундов.
В первой строке записаны два числа n и k ( 1 ≤ n , k ≤ 5·10 5 ) - количество раундов и волшебное число. Во второй строке через пробел перечислены n чисел a 1 , a 2 , ..., a n ( 1 ≤ a i ≤ 10 9 ), где a i - номер одноклассника, лучше всех написавшего i раунд. В третьей строке записано единственное число q - количество запросов. В следующих q ( 1 ≤ q ≤ 5·10 5 ) строках вводятся запросы, каждый из которых описывается двумя числами l i и r i ( 1 ≤ l i ≤ r i ≤ n ) где l i и r i - границы i -го подотрезка, на котором вам необходимо найти номер какого-нибудь волшебного одноклассника.
Выведите q чисел в отдельных строках — ответы на запросы в том порядке, в котором они заданы во входных данных. Для каждого запроса требуется вывести - 1 , если для данного подотрезка не существует волшебного одноклассника, иначе вывести номер любого из волшебных одноклассников.
Решения, работающие при 1 ≤ n , q ≤ 5000 , будут оцениваться из 10 баллов.
Решения, работающие при 1 ≤ n , q ≤ 100 000 , будут оцениваться из 35 баллов.
Решения, работающие при 1 ≤ n , q ≤ 300 000 , будут оцениваться из 60 баллов.
Решения, работающие при 1 ≤ n , q ≤ 500 000 , будут оцениваться из 100 баллов.
В первом тесте как на подотрезке (1, 3) , так и на подотрезке (2, 4) число 1 присутствует дважды.
Во втором тесте в первом, втором и пятом запросах нет ни одного числа, которое бы присутствовало дважды на отрезке запроса. В третьем запросе на подотрезке дважды присутствует число 2 ( a 3 = 2 , a 5 = 2 ), в четвёртом запросе на подотрезке дважды присутствует число 1 ( a 1 = 1 , a 6 = 1 ).
4 2 1 2 1 1 2 1 3 2 4
1 1
6 2 1 4 2 3 2 1 5 1 2 1 3 3 6 1 6 2 4
-1 -1 2 1 -1