Oh Sweet Beaverette

题意翻译

有n棵树，每一棵树都有一个美丽值。可以砍倒任意一棵树，需要满足一下要求： 1.美丽值总和尽可能的大。 2.第1棵树和第n棵树的美丽值必须相等。 3.最少剩余2棵树 ## 输入格式 第一行一个整数n。 第二行n个整数为第i棵树的美丽值 ## 输出格式 第一行两个数，分别代表美丽值总和，砍倒的树的数量。 第二行输出解决方案。若有多个解决方案则输出任何一种。

题目描述

— 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?

输入输出格式

输入格式

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 $ 10^{9} $ 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·10^{5} $ (subproblems 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.

输入输出样例

输入样例 #1

5
1 2 3 1 2

输出样例 #1

8 1
1 

输入样例 #2

5
1 -2 3 1 -2

输出样例 #2

5 2
2 5