Лови бонус
(Время: 3 сек. Память: 64 Мб Сложность: 45%)
В легендарной онлайн игре разработчики решили организовать подарок каждому игроку. Они подготовили массив A из N целых чисел. Игрок, не зная массив, может выбирать отрезок [L, R], такой что 1 ⩽ L ⩽ R ⩽ N, и навсегда прокачать своего персонажа, получив бонус к урону, равному произведению чисел с этого отрезка у массива A, то есть AL × AL+1 × ... × AR.
Всего в этой акции почувствовало M игроков, где каждый выбрал отрезок [Li, Ri]. Теперь разработчики хотят составить список игроков, упорядоченный по неубыванию полученного бонуса. Из-за необъяснимых причин их программа до сих пор не может выдать результат, поэтому они просят помощи у вас!
Игроки считаются упорядоченными по неубыванию, если каждый игрок в списке, кроме первого, имеет бонус, больший или равный предыдущему.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N — размер массива A (1 ⩽ N ⩽ 105).
Вторая строка содержит n целых чисел Ai (-2 ⩽ Ai ⩽ 2).
В третьей строке содержится целое число M — количество игроков (1 ⩽ M ⩽ 2 × 105).
Каждая из следующих M строк содержит по два целых числа Li и Ri— отрезок игрока (1 ⩽ Li ⩽ Ri ⩽ N).
Выходные данные
В выходной файл OUTPUT.TXT выведите M различных чисел Pi (1 ⩽ Pi ⩽ M), означающих порядок, в котором игроки упорядочены по неубыванию.
При наличии нескольких решений выведите любое.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
-1 0 1 2 -2
4
1 1
1 5
4 5
3 4 | 3 1 2 4 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
