Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Заверните две!

(Время: 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.TXTOUTPUT.TXT
15
5 1 2 -3 1
3
1 4
2 3
4 5
2 3
23
1 2 3
2
1 2
2 3
-1 -1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 A. Архимед
 B. Верхняя граница
 C. Волшебные цветы
 D. Двоичное упражнение
 E. Stack Unwinding
 F. Пробежка
 G. Три монеты
 H. Кинозал
 I. Индикатор загрузки
 J. Заверните две!
 K. Сладкая вата

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru