测试数据来自 system/3066

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) 堆核物质，用 \(N\) 条边把它们连接成一个环形，第 \(1\) 条边连接 \(w[n]\) 和 \(w[1]\)，对于 \(i>1\) 时，第 \(i\) 条边连接着 \(w[i-1]\) 和 \(w[i]\)，并且每条边上标有一个运算符+（加）或者*（乘），其中第 \(i\) 堆核物质的能量值为 \(w[i]\)。如图所示（ \(N=4\)）：

　　需要你把 \(N\) 堆核物质聚合成一堆。聚合时，首先选中一条边删除；接下来进行 \(N-1\) 次聚合，每一次聚合都会选择一条边删除，把这条边以及该边连接的两堆核物质聚合成一个新堆，新堆的能量值等于两堆核物质能量值就是按照删除边上标有的运算符进行计算得到的结果。最终能量值就是最后得到的那一堆的能量值。如下图是一次聚合的过程，最终能量值为 0：

　　那么，你需要知道最终得到的最高能量值是多少？以及首先应该删除哪条边才能得到这个最高值？

【输入格式】

　　第一行为整数 \(N\)，表示有 \(N\) 堆核物质和 \(N\) 条边。
　　第二行描述了环形上运算符和顶点上的整数，从编号为 1 的边开始，边、核物质、边、核物质、…，按顺序描述，数据之间用一个空格隔开。

【输出格式】

　　输出两行：其中第一行输出最高能量值，第二行输出第一次删除的边的标号，若有多个，按标号从小到大输出。

【输入输出样例】

　Input

4
+ -7 + 4 * 2 * 5

　Output

33
1 2

【数据限制】

　　100%的数据满足：\(1≤n≤100\)，数据保证无论何时，顶点上的数值都在\([-10^9,10^9]\)之内。

【来源】

　　Mr.he