Беси радовалась введённому индивидуальному обучению.
К несчастью её тьютор Фермер Джон очень скучный лектор, и поэтому она часто
засыпала во время занятий.
ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии.
Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\)
(\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний
на всех занятиях не превышает \(10^{18}\).
Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз
на каждом занятии.
Единственный способ Эльзы модифицировать свои записи - объединить два соседних
занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\)
тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\)
Если Эльза выберет разделить третье занятие на два, то лог может стать одним из
\([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).
По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее
любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить
минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка каждого теста содержит \(N\), а вторая содержит \(a_1,a_2,\ldots,a_N\).
Третья строка содержит \(Q\) - количество запросов, за которым следует \(Q\) строк
с целым числом \(q_i\) - кандидат в наименее любимое число Беси.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого \(q_i\) вычислите минимальное количество модификаций, которое
требуется для Эльзы, чтобы конвертировать лог в \(q_i\) или выведите \(-1\),
если это невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 3 1 1 4
7
1
2
3
4
5
6
12
|
6
6
4
5
-1
4
5
|