дп

Штурманский журнал «Нулевого указателя» содержит n записей о курсах корабля — каждая запись это целое число (градусы поворота за день). Капитан Архипов считает, что самый красивый маршрут — это когда курсы идут строго последовательными целыми числами: x, x+1, x+2, … Он называет это Великой Цепью.

Найдите наидлиннейшую подпоследовательность записей (не обязательно подряд), которая образует Великую Цепь. Выведите её длину и номера записей в журнале. Если существует несколько подпоследовательностей максимальной длины — можно вывести любую.

«И не вздумай вывести только длину», — добавил Архипов, не отрываясь от чая.

Первая строка: n (1 ≤ n ≤ 200 000).

Вторая строка: n чисел a_i (1 ≤ a_i ≤ 10⁹) — курсы по дням.

Первая строка: длина наибольшей Великой Цепи.

Вторая строка: номера записей в порядке возрастания (нумерация с 1).

 

Примечание: Журнал: 5 3 1 2 4 1 3 (7 записей).

Записи №3, 4, 5, 7 имеют курсы 1, 2, 3, 4 — они идут подряд с шагом 1, образуя Великую Цепь длиной 4.

Например, записи №1, 2, 7 дают курсы 5, 3, 3 — не подходят (не последовательные).

Записи №6, 4, 5 дают 1, 2, 4 — тоже не подходят (пропущено 3).

Если существует несколько подпоследовательностей максимальной длины — можно вывести любую.

Шкипер Баг ужасно страдает от морской болезни. Единственное спасение — зелье «Штиль», которое продаётся в лавках на островах архипелага. На n островах цены разные: в i-м порту бутылка стоит xi дублонов.

Каждый раз, когда «Нулевой указатель» заходит в порт, у Шкипера Бага с собой разная сумма — зависит от того, не украл ли корабельный кот монеты из кармана. Всего таких заходов будет q. Для каждого захода Шкипер Баг хочет заранее знать: в скольких портах архипелага он смог бы купить зелье, имея столько дублонов?

Формат входных данных
Первая строка: n (1≤n≤100 000) — количество портов.
Вторая строка: n чисел  xi​ (1≤xi≤100 000) — цены на зелье.
Третья строка: q (1≤q≤100 000) — количество заходов в порт.
Следующие q строк: число mi​ (1≤mi≤10⁹) — дублоны Шкипера Бага при i-м заходе.

Формат выходных данных
q чисел — для каждого захода количество портов, где хватит денег.


Примечание: 
При 1 дублоне ни одна лавка недоступна. При 8 — можно купить в 4 лавках (цены 2, 3, 4, 7). При 3 — только одна лавка (цена 2). При 100 дублонах — все пять.