Задача . Безопасный коридор

Безопасный коридор

Космический корабль состоит из N отсеков, расположенных последовательно и пронумерованных от 1 до N. Прочность отсека i равна a_i.

Спасательный модуль может войти через любой отсек с номером i, после чего проходит через все отсеки от i до N включительно. Для безопасного прохода модуля с грузом массы X прочность каждого отсека на пути должна быть не меньше X.

Дано Q независимых заявок с массами грузов X. Для каждой заявки найдите наименьший номер отсека, с которого можно начать движение и безопасно дойти до конца корабля.

Если безопасный проход невозможен ни с одного отсека, выведите -1.

Входные данные

В первой строке задано N (1 ≤ N ≤ 200000). Во второй строке записаны N целых чисел a_i (0 ≤ a_i ≤ 1000000000).

В третьей строке задано Q (1 ≤ Q ≤ 200000). В следующих Q строках записано по одному числу X (0 ≤ X ≤ 1000000000).

Выходные данные

Для каждой заявки выведите ответ в отдельной строке.

6
7 2 8 6 9 5
5
1
3
5
6
8

1
3
3
-1
-1