CF1700D River Locks

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. The picture illustrates $ 5 $ locks with two open pipes at locks $ 1 $ and $ 3 $ . Because locks $ 1 $ , $ 3 $ , and $ 4 $ are already filled, effectively the water goes to locks $ 2 $ and $ 5 $ .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 \le n \le 200\,000 $ ) — the number of locks. The second lines contains $ n $ integers $ v_1, v_2, \dots, v_n $ ( $ 1 \le v_i \le 10^9 $ )) — volumes of the locks. The third line contains one integer $ q $ ( $ 1 \le q \le 200\,000 $ ) — the number of queries. Each of the next $ q $ lines contains one integer $ t_j $ ( $ 1 \le t_j \le 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 $ queries in the first example test. In the queries $ 1, 3, 4 $ the answer is $ -1 $ . We need to wait $ 4 $ seconds to fill the first lock even if we open all the pipes. In the sixth query we can open pipes in locks $ 1 $ , $ 3 $ , and $ 4 $ . After $ 4 $ seconds the locks $ 1 $ and $ 4 $ are full. In the following $ 1 $ second $ 1 $ liter of water is transferred to the locks $ 2 $ and $ 5 $ . The lock $ 3 $ is filled by its own pipe. Similarly, in the second query one can open pipes in locks $ 1 $ , $ 3 $ , and $ 4 $ . In the fifth query one can open pipes $ 1, 2, 3, 4 $ .