Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Chocolate

By shefin · Limits 2s, 512 MB

There is a shop named Chocolove in the Codeland. There are many chocolates in the shop. Each chocolate has its own taste value. You want to take some chocolates from this shop. But the chocolates are not free. You have to pay. If you take chocolate i and the previous chocolate you took is j, the cost of taking chocolate i is the difference between i*Tj and j*Ti where Ti, Tj is the taste value of chocolate i and j respectively. Remember, you can’t take chocolate i more than once. The shop has an offer too. The cost of the chocolate you take first is 0.
Now you want to know what is the minimum amount of money you have to pay if you take x chocolates from the shop.

Input

The first line of the input contains an integer N, the number of chocolates. The next line contains N integers separated by a space, ith integer denotes the taste value of ith chocolate.
The next line contains an integer Q, the number of queries. The next Q lines will contain values denoting each query. In each query, there will be an integer x, the number of chocolates you want to take from the shop.

Constraints:
1 <= N <= 19
0 <= Taste Value <= 109
1 <= Q <= 105
1 <= x <= N

Output

For each query, print the minimum amount of money you have to pay in a single line if you take x chocolates from the shop

Sample

InputOutput
3
17 90 81
2
3
2
86
30



Notes:

In the first query, one of the best ways is taking chocolates in this order: 2, 1, 3.
The cost of taking chocolate 2 is 0.
The cost of taking chocolate 1 is the difference between 1*90 and 2*17 which is 56.
The cost of taking chocolate 3 is the difference between 3*17 and 1*81 which is 30.
So, the amount of money you have to pay = 0+56+30 = 86.



Discussion
Statistics

67% Solution Ratio

m1n2o3Earliest, 4w ago

mahdi.hasnatFastest, 0.3s

m1n2o3Lightest, 81 MB

m1n2o3Shortest, 807B

Submit

Login to submit