← 返回题目列表

Codeforces · 331/A1

A1. 哦,甜蜜的海狸

中文机器翻译题面 查看原题

— 哦,我亲爱的比弗雷特,你想和我一起沿着美妙的林地带散步吗?

— 当然,我的智能海狸!让我们一起欣赏这美丽的景色吧。周五晚上怎么样?

这时,智能海狸开始冲了。到周五一切都会很完美,所以他需要为即将到来的步行准备腰带。他需要砍倒几棵树。

让我们将林带视为一系列树木。每棵树 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