— 哦,我亲爱的比弗雷特,你想和我一起沿着美妙的林地带散步吗?
— 当然,我的智能海狸!让我们一起欣赏这美丽的景色吧。周五晚上怎么样?
这时,智能海狸开始冲了。到周五一切都会很完美,所以他需要为即将到来的步行准备腰带。他需要砍倒几棵树。
让我们将林带视为一系列树木。每棵树 i 都由审美吸引力 ai 来描述 - 有些树非常美观,有些树“马马虎虎”,而有些树则非常丑陋!
聪明的海狸计算出,他需要以下效果才能赢得海狸的芳心:
- 第一个目标是取悦海狸:剩余树木的审美吸引力之和必须尽可能大;
- 第二个目标是让 Beaverette 感到惊讶:生成的带中第一棵树和最后一棵树的审美吸引力必须相同;
- 当然,步行应该成功:林带中必须至少剩下两棵树。
现在帮助智能海狸吧!他需要砍掉哪些树才能赢得海狸的芳心?
输入
第一行包含一个整数 n — 林地带中树木的初始数量,2 ≤ n。第二行包含空格分隔的整数 ai — 每棵树的审美吸引力。所有审美吸引力的绝对值均不超过109。
- 要获得 30 分,需要解决具有约束条件的问题:n ≤ 100(子问题 A1);
- 要获得 100 分,您需要解决具有约束条件的问题:n ≤ 3·105(子问题 A1+A2)。
输出
第一行打印两个整数——智能海狸干预后林带的总审美吸引力和砍伐树木的数量k。
在下一行中打印 k 个整数——海狸需要砍伐的树木数量。假设树从左到右编号为 1 到 n。
如果有多个解决方案,请打印其中任何一个。保证至少两棵树具有相同的审美吸引力。
示例
输入 #1
5 1 2 3 1 2
输出 #1
8 1 1
输入 #2
5 1 -2 3 1 -2
输出 #2
5 2 2 5