题目描述

——哦，我甜美的海狸小姐，愿意和我一起沿着美妙的林间小道散步吗？

——当然愿意，我聪明的海狸！让我们一同欣赏壮丽的风景。周五晚上如何？

此时聪明的海狸开始忙活起来：一切都要在周五前准备妥当，他得为即将到来的散步整理林带——也就是砍掉几棵树。

把林带看作一列树。每棵树 $i$ 用美观度 $a_i$ 描述——有的树非常好看，有的树普普通通，还有的树简直丑得没法看！

聪明的海狸算了算，要赢得海狸小姐的芳心，需要达到以下效果：

• 第一目标是取悦小姐：留下的树的美观度总和必须最大；
• 第二目标是给小姐惊喜：留下的林带中第一棵和最后一棵树的美观度必须相同；
• 当然，散步必须顺利：林带中至少要留下两棵树。

现在帮帮聪明的海狸：他需要砍掉哪些树？

输入格式

第一行包含一个整数 $n$（$n \ge 2$），表示林带里最初的树数。第二行包含用空格隔开的整数 $a_i$，表示每棵树的美观度。所有美观度的绝对值都不超过 $10^9$。

• 获得 30 分的数据：$n \le 100$（子问题 A1）；
• 获得 100 分的数据：$n \le 3 \cdot 10^5$（子问题 A1+A2）。

输出格式

第一行输出两个整数——聪明的海狸整理后林带的美观度总和，以及砍掉的树数 $k$。

第二行输出 $k$ 个整数——需要砍掉的树的编号（树从左到右按 1 到 $n$ 编号）。

如有多组解，输出任意一组。保证至少有两棵树的美观度相同。

5
1 2 3 1 2

8 1
1

5
1 -2 3 1 -2

5 2
2 5