Бесі раділа введеному індивідуальному навчанню. На жаль її тьютор Фермер Джон дуже нудний лектор, і тому вона часто засинала під час занять.

ФД попросив Ельзу записувати кількість разів, коли Бесі засинала на кожному занятті. Всього було \(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}\)), для кожного з них допоможіть Ельзі обчислити мінімальну кількість модифікацій лога, щоб усі числа у ньому стали однаковими.

Формат вхідних даних

Перший рядок кожного тесту містить \(N\), а другий містить \(a_1,a_2,\ldots,a_N\). Третій рядок містить \(Q\) - кількість запитів, за якими слідує \(Q\) рядків з цілим числом \(q_i\) - кандидат у найменш улюблене число Бесі.

Формат вихідних даних

Для кожного \(q_i\) обчисліть мінімальну кількість модифікацій, яка потрібна для Ельзи, щоб конвертувати лог в \(q_i\) або виведіть \(-1\), якщо це неможливо.

Приклад вхідних даних

6
1 2 3 1 1 4
7
1
2
3
4
5
6
12

Приклад вихідних даних

6
6
4
5
-1
4
5

Ельзі потрібно зробити як мінімум 4 модифікації, щоб конвертувати його у всі трійки:

  1 2 3 1 1 4
  3 3 1 1 4
  3 3 1 5
  3 3 6
  3 3 3 3

Неможливо конвертувати лог у всі 5-ки тому для даного кандидата відповідь \(-1\).

ОЦІНЮВАННЯ:

• У тестах 2-4, \(N,Q\le 5000\)

• У тестах 5-7, все \(a_i\) не більше \(10^9\).

• У тестах 8-26 немає додаткових обмежень.

  Авторы: Jesse Choe и Benjamin Qi