Решение задачи Приравнивание цен с Codeforces

В магазине продается n предметов. Цена i-го предмета равна ai. Владелец магазина хочет приравнять цены всех предметов. Но он хочет изменить цены аккуратно.

Фактически, владелец магазина может изменять цену какого-то предмета i таким образом, что разница между старой ценой этого предмета ai и новой ценой bi не превышает k. Другими словами, должно выполняться условие |ai−bi|≤k (|x| — это абсолютное значение x).

Он может изменять цену каждого предмета не более одного раза. Заметьте, что он может оставить старые цены некоторым предметам. Новая цена bi каждого предмета i должна быть положительной (то есть должно выполняться условие bi>0 для всех i от 1 до n).

Ваша задача — найти максимально возможную равную цену B всех предметов с ограничением, что для всех предметов должно выполняться условие |ai−B|≤k (где ai равно старой цене предмета, а B — это одинаковая новая цена всех предметов) или сказать, что невозможно найти такую цену B.

Заметьте, что выбранная цена B должна быть целой.

Вам необходимо ответить на q независимых запросов.