B'Recently in Divanovo, a huge river locks system was built. There are now n locks, the i -th of them has the volume of v_i liters, so that it can contain any amount of water between 0 and v_i liters. Each lock has a pipe attached to it. When the pipe is open, 1 liter of water enters the lock every second. The locks system is built in a way to immediately transfer all water exceeding the volume of the lock i to the lock i + 1 . If the lock i + 1 is also full, water will be transferred further. Water exceeding the volume of the last lock pours out to the river. Note that the volume of the i -th lock may be greater than the volume of the i + 1 -th lock. To make all locks work, you need to completely fill each one of them. The mayor of Divanovo is interested in q independent queries. For each query, suppose that initially all locks are empty and all pipes are closed. Then, some pipes are opened simultaneously. For the j -th query the mayor asks you to calculate the minimum number of pipes to open so that all locks are filled no later than after t_j seconds. Please help the mayor to solve this tricky problem and answer his queries. The first lines contains one integer n ( 1 <= n <= 200 ,000 ) -- the number of locks. The second lines contains n integers v_1, v_2, ... , v_n ( 1 <= v_i <= 10^9 )) -- volumes of the locks. The third line contains one integer q ( 1 <= q <= 200 ,000 ) -- the number of queries. Each of the next q lines contains one integer t_j ( 1 <= t_j <= 10^9 ) -- the number of seconds you have to fill all the locks in the query j . Print q integers. The j -th of them should be equal to the minimum number of pipes to turn on so that after t_j seconds all of the locks are filled. If it is impossible to fill all of the locks in given time, print -1 . There are 6 queri'...