最惨烈的代价
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

“我对三体世界说话。”罗辑说,声音并不高,他本想重复一遍,但是没有,他知道对方能听到。

这个仍未醒来的世界,不知道自己已被当做一场豪赌的筹码,放到了宇宙的赌桌上。

在智子无孔不入的进攻下,面壁者们的计划依次告吹,唯有人类的执剑人——罗辑,依然在和智子对抗。接下来,罗辑需要和智子进行 N 场博弈。

人类的力量是很渺小的,为了胜利,罗辑可以付出一些惨烈代价。在 N 场博弈中,只要一方获胜次数大于一半,博弈立刻分出胜负。也就是说,只要智子在博弈中获胜了 (N+1)/2 局,人类就会陷入万劫不复的境地!

罗辑想要拯救人类,而他的智慧足以让他预见到未来 N 场博弈中每一场的代价 a_i,请你帮他求出要想成功战胜智子,最少需要付出多少代价?

请你按下标递增的顺序输出详细方案。

输入描述:

第一行输入一个整数 N(1\le N\le 5\times 10^6),保证 N 为奇数,代表罗辑与智子共有 N 场博弈。

第二行输入 N 个整数 a_i(0\le a_i\le 10^9),代表罗辑在第 i 场博弈中获胜需要付出的代价。

输出描述:

第一行输出一个整数,代表罗辑要想战胜智子所需要付出的最小代价。

第二行给出详细方案,即罗辑需要选择哪几场博弈获胜,才能以最小代价取得最终胜利?请你有序输出选择的序列。注意,如果两场博弈的代价相同,罗辑为了稳妥起见会优先选择序号小的那一场。
示例1

输入

复制
5
1 7 6 3 2

输出

复制
6
1 4 5
示例2

输入

复制
11
3 5 7 4 5 10 1 6 2 5 3

输出

复制
18
1 2 4 7 9 11

备注:

本题数据量比较大,你需要考虑关闭同步流或使用更快的输入输出方式。

请注意本题的数据范围并选择复杂度合适的算法。