Заверните две!
(Время: 5 сек. Память: 64 Мб Сложность: 54%)
Петя как обычно шёл утром на работу по обычной дороге, как вдруг ему на глаза попалась новая шаурмичная. Он решил зайти в неё и запастись пищей на весь следующий день. Петя хочет купить ровно две шаурмы — на обед и ужин (не беспокойтесь, микроволновка на работе у Пети есть).
Всего в шаурмичной существует N ингредиентов, пронумерованных от 1 до N, и M рецептов шаурмы. Каждый рецепт для удобства представляет из себя отрезок [Li, Ri], и означает, что в i-й рецепт входят ингредиенты с номерами от Li до Ri включительно.
Петя быстрым взглядом ознакомился со всеми ингредиентами и оценил каждый i-й ингредиент целым числом Ai — насколько ему нравится этот продукт. Естественно, Петя хочет получить максимально возможное суммарное удовольствие от приёма пищи. Удовольствие от одной шаурмы равно сумме всех Ai входящих в неё ингредиентов.
Так же, Петя хочет разнообразия — выбранные рецепты не должны иметь общего ингредиента.
Помогите Пете с нелёгким выбором, определите, какие две шаурмы нужно заказать, чтобы условия были выполнены, а он в качестве благодарности угостит вас как-нибудь шаурмой.
Входные данные
Первая строка входного файла INPUT.TXT содержит целое число N — количество ингредиентов (1 ≤ N ≤ 2×105).
Во второй строке содержатся N целых чисел Ai (|Ai| ≤ 109).
Третья строка содержит целое число M — количество рецептов (2 ≤ M ≤ 2×105.
Следующие M строк содержат пары чисел Li и Ri — границы i-го отрезка (1 ≤ Li ≤ Ri ≤ N).
Выходные данные
В выходной файл OUTPUT.TXT выведите номера рецептов, которые стоит выбрать Пете. Если же выбрать невозможно, выведите «-1 -1».
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
5 1 2 -3 1
3
1 4
2 3
4 5 | 2 3 |
| 2 | 3
1 2 3
2
1 2
2 3 | -1 -1 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
