CF331A1.Oh Sweet Beaverette

— Oh my sweet Beaverette, would you fancy a walk along a wonderful woodland belt with me?

— Of course, my Smart Beaver! Let us enjoy the splendid view together. How about Friday night?

At this point the Smart Beaver got rushing. Everything should be perfect by Friday, so he needed to prepare the belt to the upcoming walk. He needed to cut down several trees.

Let's consider the woodland belt as a sequence of trees. Each tree i is described by the esthetic appeal a__i — some trees are very esthetically pleasing, others are 'so-so', and some trees are positively ugly!

The Smart Beaver calculated that he needed the following effects to win the Beaverette's heart:

• The first objective is to please the Beaverette: the sum of esthetic appeal of the remaining trees must be maximum possible;
• the second objective is to surprise the Beaverette: the esthetic appeal of the first and the last trees in the resulting belt must be the same;
• and of course, the walk should be successful: there must be at least two trees in the woodland belt left.

Now help the Smart Beaver! Which trees does he need to cut down to win the Beaverette's heart?

—— 哦，我亲爱的贝弗蕾特，你愿意和我一起漫步在那片美妙的林带中吗？
—— 当然愿意，我聪明的贝弗！让我们一同欣赏这壮丽的景色吧。周五晚上如何？

此时，聪明的贝弗立刻忙了起来。一切必须在周五前准备就绪，因此他需要为即将到来的漫步提前整理好这片林带——砍掉若干棵树。

我们将这片林带视为一排树木的序列。每棵树 $i$ 由其美学吸引力 $a_i$ 描述——有些树极其赏心悦目，有些则平平无奇，而还有一些树则堪称丑陋！

聪明的贝弗经过计算，得出以下目标，以赢得贝弗蕾特的芳心：

• 首要目标是取悦贝弗蕾特：剩余树木的美学吸引力之和必须达到最大可能值；
• 次要目标是令贝弗蕾特惊喜：最终林带中第一棵与最后一棵树的美学吸引力必须相等；
• 当然，漫步必须圆满成功：林带中至少需保留两棵树。

现在，请帮助聪明的贝弗！他究竟需要砍掉哪些树，才能赢得贝弗蕾特的芳心？

The first line contains a single integer n — the initial number of trees in the woodland belt, 2 ≤ n. The second line contains space-separated integers a__i — the esthetic appeals of each tree. All esthetic appeals do not exceed 109 in their absolute value.

• to get 30 points, you need to solve the problem with constraints: n ≤ 100 (subproblem A1);
• to get 100 points, you need to solve the problem with constraints: n ≤ 3·105 (subproblems A1+A2).

第一行包含一个整数 $n$ —— 林带中初始的树木数量，满足 $2 \leq n$。
第二行包含 $n$ 个用空格分隔的整数 $a_i$ —— 每棵树的美学吸引力值。所有美学吸引力值的绝对值均不超过 $10^9$。

• 若要获得 30 分，你需要在约束条件 $n \leq 100$ 下解决该问题（子问题 A1）；
• 若要获得 100 分，你需要在约束条件 $n \leq 3 \cdot 10^5$ 下解决该问题（子问题 A1 + A2）。

In the first line print two integers — the total esthetic appeal of the woodland belt after the Smart Beaver's intervention and the number of the cut down trees k.

In the next line print k integers — the numbers of the trees the Beaver needs to cut down. Assume that the trees are numbered from 1 to n from left to right.

If there are multiple solutions, print any of them. It is guaranteed that at least two trees have equal esthetic appeal.

第一行输出两个整数——河岸林带经聪明海狸干预后的总美学吸引力值，以及被砍伐的树木数量 $k$。

第二行输出 $k$ 个整数——海狸需要砍伐的树木编号。假设树木从左到右依次编号为 $1$ 到 $n$。

若存在多种解，输出任意一种即可。题目保证至少有两棵树具有相同的美学吸引力值。