Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


7. Гистограмма

Автор задачи: Купрейчик Антон
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 2 с.
Ограничение по памяти: 128 МБ

«Статистика — наше все» — именно это повторял себе бухгалтер Тимур в каждый из своих рабочих дней. И вот в один из этих дней, генеральный директор дает ему задание по сбору статистики. По заданию он будет получать информацию о зарплате каждого из n сотрудников его компании. Эта информация представляет собой гистограмму, где для каждого сотрудника отведена своя ячейка. Данные гистограммы могут изменяться — для определенного сотрудника зарплата может измениться на d условных единиц. Суть данной статистики в том, чтобы узнавать среднюю заработную плату среди всех работников и сотрудника, зарплата которого ближе всего к средней.

Тимур поддерживает такую статистику уже три года, а Вы сможете?

Входные данные

В первой строке входных данных задано число n — количество сотрудников в компании Тимура (1 ≤ n ≤ 105). В следующей строке дано n целых положительных чисел, не превосходящих 106, — значения величины заработной платы для каждого из сотрудников.

Следующей строка содержит целое число m (1 ≤ m ≤ 105) — количество запросов к данным. В каждой из последующих m строк задано описание очередного запроса: если в начале запроса следует число 1, то это — запрос на получение номера сотрудника (запрос первого типа), зарплата которого ближе всего к средней, если же в начале запроса следует число 2, то это — запрос на изменение зарплаты (запрос второго типа), и далее через пробел задано два целых числа pi (1 ≤ pin) — номер сотрудника и di (0 ≤ |di| ≤ 103) — величина, на которую увеличилась зарплата.

Выходные данные

В выходных данных для каждого из запросов первого типа необходимо вывести в отдельной строке два целых числа через пробел: номер искомого сотрудника и величину его заработной платы. Если же существует несколько таких сотрудников, то следует вывести сотрудника с наименьшей величиной зарплаты. Если и таких сотрудников несколько, то среди них необходимо выбрать сотрудника с наименьшим номером.

Примеры
Стандартный вводСтандартный вывод
3
1 2 3
5
1
2 1 2
1
2 2 1
1
2 2
1 3
1 3