Реалізуйте дерево відрізків для знаходження накоротшого префіксу масиву сума якого буде більша або рівна заданому числу.

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

В першому рядку ціле число \(N\), кількість елементів масиву (\(1 \le N \le 10^5\)).
В другому рядку елементи масиву. (\(0 \le Ai \le 10^5\))
В третьому рядку вводиться число \(P\) - кількість запитів (\(1 \le P \le 3*10^4\))
В кожному з наступних \(P\) рядків міститься по одному числу - сума яку необхідно набрати на префіксі масиву.

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

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

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

5
2 2 2 1 5 
4
5
7
0
100

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

3 4 0 -1

Пояснення до прикладу

В першому запиті необхідно набрати суму 5, для цього необхідно буде взяти елементи 2+2+2=6 В другому запиті необхідно набрати суму 7, для цього необхідно буде взяти елемента 2+2+2+1=7 В третьому запиті необхідно набрати суму 0, а для цього потрібно 0 елементів. В четвертому запиті необхідно набрати суму 1000, а це неможливо