Escape the Planet Earth
As you know earth is affected by corona virus. Situation becomes worse day by day .Almost 80% people on earth is affected .So scientist take a decision, they will send some people to nearest safe planet (N~76),which is same as earth but far away from earth .This is too dangerous to send people such an unknown planet, but there is no way. Scientist tried for many years to find medicine for the virus. Now virus becomes very strong and who is affected by this died in 5 days.
So escaping is the only solution. To escape the earth we need to collect a ticket of spacecraft. One can collect a ticket if he can satisfy the pilot. To satisfy a specific pilot one needs to give him some money. Initially you don’t have any money . Now you have to collect money. To collect money you have to play a game (“EASY”) which is cost free. The game has at most 30 level, if you play a level you will get some money. Each level contains some money. You don’t need to start from level 1, and you can skip any level if you want, but you can’t play same level twice. If you play some level you must have to collect all the money that the level has, you can’t collect partial money.
Your target is to play the game in such a way so that the collected money satisfy the specific pilot.
Determine how many ways you can play the game such that you can escape the earth.
Input
The first line of input will contain a single integer n(1 ≤ n ≤ 30),the levels of the game.
Next line contains n space separated integer a1.....an(0 ≤ ai ≤ 1012 ),the money contains level ai.
Next line contains a integer q (1 ≤ q ≤ 100),the number of queries.
Next q lines will contain two integers l,r,(1 ≤ l , r ≤ 1018),the satisfaction money of qth pilot. That means ,if the pilot get money in range [l-r] (inclusive) ,he will give you a ticket.
Output
For each query print in a new line, how many ways you can play the game such that you can escape the planet earth.
Sample
| Input | Output |
|---|---|
5 1 2 3 4 5 1 1 5 | 9 |
{1},{2},{3},{4},{5},{1,2},{1,3},{1,4},{2,3},these are the 9 possible game level set ,by which you can satisfy the pilot. | |
