Market Shopping

Interview

Time limit10sMemory limit256 MB

Summary

You choose exactly k prices per query to maximize the odd total, printing -1 when no odd sum exists.

Level: Medium5 of 10
Topics: Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

Every morning the grandmother goes to the market and buys a few products. Her grandson noticed that the amount she pays is always an odd number, and that every grandmother in the region shops the same way.

The market sells $n$ products, and the grandmother buys at most one copy of each. She does not want to carry more money than she needs. One day she asked her grandson how much money to take if she plans to buy exactly $k$ products that day. The grandson does not know which products she will pick, so the amount has to be enough for any choice of $k$ products whose prices add up to an odd number.

In other words, choose exactly $k$ of the $n$ products so that the sum of their prices is odd, and report the largest such sum. The same question comes up on several days, so the grandson writes a program that reads all prices once and answers each question.

Input

The first line contains the number of products on the market, $n$ ( $1 \le n \le 10^6$ ). The second line contains the $n$ prices separated by spaces; each price is an integer between $1$ and $10^9$ . The third line contains the number of days $m$ ( $1 \le m \le 10^6$ ) that the grandson still spends at his grandmother's house. Each of the next $m$ lines contains one integer $k_i$ ( $1 \le k_i \le n$ ), the number of products the grandmother plans to buy that day.

Output

Print $m$ lines. On line $i$ , print the largest odd total price over all ways to choose exactly $k_i$ products. If no choice of $k_i$ products has an odd total price, print -1 on that line.

Examples3

Example 1
Input
```
4
4 2 1 3
3
2
3
4
```
Expected output
```
7
9
-1
```
Example 2
Input
```
1
7
1
1
```
Expected output
```
7
```
Example 3
Input
```
5
9 1 7 3 5
5
1
2
3
4
5
```
Expected output
```
9
-1
21
-1
25
```