题目描述

小明正在玩一个单人多边形游戏。游戏开始时，给定一个有 $N$ 个顶点的多边形，每个顶点上标有一个整数，每条边上标有运算符 $+$（加法）或 $\times$（乘法）。边从 $1$ 到 $N$ 编号。

游戏规则如下：

• 第一步，玩家必须移除一条边。
• 此后每一步，玩家选择一条边 $E$ 以及 $E$ 所连接的两个顶点 $V_1$ 和 $V_2$，将它们合并为一个新顶点，新顶点的值为 $V_1$ 和 $V_2$ 按照边 $E$ 上的运算符进行运算的结果。
• 当所有边都被移除后游戏结束，最终剩余的那个顶点上的值就是游戏得分。

玩家希望获得尽可能高的得分。请编写程序，对于给定的多边形，计算最高可能的得分，并按递增顺序列出所有能够导致该最高得分的第一步移除边的编号。

输入格式

输入包含两行。

第一行一个整数 $N$，表示多边形的顶点数。

第二行依次给出边 $1$ 到 $N$ 的运算符和对应顶点的标号，相邻元素用空格分隔。具体地，先是边 $1$ 的运算符，然后是顶点 $1$ 的标号，再是边 $2$ 的运算符，顶点 $2$ 的标号，……，最后是边 $N$ 的运算符和顶点 $N$ 的标号。运算符用字母 t（表示 $+$）或 x（表示 $\times$）表示。

保证 $3 \le N \le 50$，对任意操作序列，顶点上的数值在 $[-32768, 32767]$ 范围内。

输出格式

输出包含两行。

第一行一个整数，表示最高得分。

第二行按递增顺序输出所有能够导致该最高得分的第一步移除边的编号，编号之间用空格分隔。

样例

4
t -7 t 4 x 2 x 5

33
1 2

提示

本题为区间 DP 经典题。需要同时维护最大值和最小值，因为负数乘以负数可能得到正的最大值。