#P3721. PA2014 Final Bazarek

    ID: 2934 传统题 2000ms 128MiB 尝试: 995 已通过: 311 难度: 4 上传者: 标签>CF1500普及+/提高-排序贪心交换论证奇偶性分析一维前缀和前后缀最值鸣谢Jcvb

PA2014 Final Bazarek

题目描述

有 nn 件商品,选出其中的 kk 个,要求它们的总价为奇数,求最大可能的总价。

输入格式

第一行一个整数 nn(1≤n≤1000000)(1≤n≤1000000),表示商品数量。 接下来一行有 nn 个整数,表示每件商品的价格,范围在 [1,109][1,10^9]。 接下来一行有一个整数 mm(1≤m≤1000000)(1≤m≤1000000),表示询问数量。 接下来 mm 行,每行一个整数 kik_i(1≤ki≤n)(1≤k_i≤n)。

输出格式

对于每个询问,输出一行表示保证奇数的情况下最大的总价。若无法满足要求,输出 -1。

输入样例

4
4 2 1 3
3
2
3
4

输出样例

7
9
-1

数据范围

对于 100%100\% 的数据,1≤n≤1051 \le n \le 10^5,1≤ai≤1091 \le a_i \le 10^9,1≤m≤1051 \le m \le 10^5,1≤ki≤n1 \le k_i \le n。