Polygon

Polygon is a one-player game played on a polygon with $N$ vertices, like the one in Figure 1 where $N = 4$. Each vertex is labelled with an integer, and each edge is labelled with either + (addition) or * (multiplication). The edges are numbered from $1$ to $N$.

Figure 1. A polygon.

On the first move, one edge is removed. Every later move consists of these two steps:

• pick an edge $E$ together with the two vertices $V_1$ and $V_2$ that it links, and
• replace them with a single new vertex whose label is the result of applying $E$'s operation to the labels of $V_1$ and $V_2$.

The game ends when no edges remain, and the score is the label of the single vertex that is left.

For example, consider the polygon in Figure 1. Suppose the player first removes edge 3:

Figure 2. Removing edge 3.

then picks edge 1:

Figure 3. Picking edge 1.

then edge 4:

Figure 4. Picking edge 4.

and finally edge 2, ending with a score of 0:

Figure 5. Picking edge 2.

Write a program that, given a polygon, computes the highest score that can be reached and lists every edge that, when removed on the first move, allows a game achieving that highest score.

The input describes a polygon with $N$ vertices and consists of two lines.

The first line contains the integer $N$.

The second line lists the edge labels $1, \ldots, N$ interleaved with the vertex labels, all separated by single spaces, in this order: the label of edge 1, then the label of the vertex between edges 1 and 2, then the label of edge 2, then the label of the vertex between edges 2 and 3, and so on, ending with the label of edge $N$ followed by the label of the vertex between edges $N$ and 1.

Each edge label is the letter t (meaning +) or the letter x (meaning *).

Print the highest score obtainable for the given polygon on the first line.

On the second line, print every edge that, if removed on the first move, can lead to a game achieving that highest score. List the edges in increasing order, separated by single spaces.