| Codeforces Round 167 (Div. 2) |
|---|
| Закончено |
У Димы есть лесенка, которая состоит из n ступенек. Первая ступенька имеет высоту a1, вторая — a2, последняя — an (1 ≤ a1 ≤ a2 ≤ ... ≤ an).
Дима решил поиграться с лесенкой, поэтому он бросает сверху на лесенку прямоугольные коробки: i-тая коробка имеет ширину wi и высоту hi. Каждую коробку Дима бросает вертикально вниз на первые wi ступенек лесенки, то есть коробка покрывает ступеньки с номерами 1, 2, ..., wi. Каждая брошенная коробка летит вертикально вниз, до тех пор пока не случится хотя бы одно их двух следующих событий:
- низ коробки коснется верха одной из ступенек;
- низ коробки коснется верха одной из уже брошенных коробок.
Учитывается только касание горизонтальных сторон ступенек и коробок, при этом касание углами не учитывается. В частности из этого следует, что коробка шириной wi не может коснуться ступеньки с номером wi + 1.
Вам задано описание лесенки и последовательность, в которой Дима кидал коробки на нее. Для каждой коробки определите, на какой высоте окажется низ этой коробки после приземления. Считайте, что очередная коробка бросается уже после приземления предыдущей.
В первой строке записано целое число n (1 ≤ n ≤ 105) — количество ступенек у лесенки. Во второй строке задана неубывающая последовательность, состоящая из n целых чисел, a1, a2, ..., an (1 ≤ ai ≤ 109; ai ≤ ai + 1).
В следующей строке задано целое число m (1 ≤ m ≤ 105) — количество коробок. В каждой из следующих m строк записана пара целых чисел wi, hi (1 ≤ wi ≤ n; 1 ≤ hi ≤ 109) — размер i-той брошенной коробки.
Числа в строках разделяются пробелами.
Выведите m целых чисел — для каждой коробки высоту, на которой окажется низ этой коробки после приземления. Ответы для коробок выводите в порядке, в котором коробки заданы во входных данных.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
5
1 2 3 6 6
4
1 1
3 1
1 1
4 3
1
3
4
6
3
1 2 3
2
1 1
3 1
1
3
1
1
5
1 2
1 10
1 10
1 10
1 10
1
3
13
23
33
На картинке изображен первый тестовый пример.
