Maximum Score in Polygon Game

The game is played on a polygon with \(N\) vertices. Each vertex is labeled with an integer and each edge is labeled with either the symbol \(+\) or \(\times\) (denoted by the character *). The edges are numbered from \(1\) to \(N\) in order. In one move, a player can remove an edge (only once in the first move) and then repeatedly perform the following operation: choose an edge \(E\) (with label either \(+\) or \(\times\)) that connects two vertices \(V_1\) and \(V_2\), and merge these two vertices into a new vertex with label equal to \(V_1 \; E \; V_2\) (i.e. add if the symbol is \(+\) or multiply if the symbol is \(\times\)). This process is repeated until no edge remains. The final score of the game is the label on the single remaining vertex.

Your task is to determine the highest possible final score obtainable by playing optimally, and list all the edges (by their numbers) that, when removed in the first move, can lead to a game with that maximum score.

Note: After the removal of an edge, the polygon becomes a chain. If the polygon has vertices \(V_1,V_2,\dots,V_N\) (in cyclic order) and edges \(E_1,E_2,\dots,E_N\) (where \(E_i\) connects \(V_i\) and \(V_{i+1}\), with \(V_{N+1}\) interpreted as \(V_1\)), then removing edge \(i\) produces a chain with vertices \(V_{i+1}, V_{i+2},\dots,V_N, V_1,\dots,V_i\) and with the remaining edges in the corresponding cyclic order.

It is guaranteed that the numbers and the operations are such that an optimal parenthesization (i.e. merge order) exists and all intermediate results (as well as the final score) will fit in a 64-bit integer.

inputFormat

The first line contains an integer \(N\) (the number of vertices).

The second line contains \(N\) integers \(V_1,V_2,\dots,V_N\), representing the labels on the vertices in order.

The third line contains a string of exactly \(N\) characters. Each character is either + or * representing the operation on the corresponding edge. The \(i\)th character corresponds to the edge connecting vertex \(V_i\) and vertex \(V_{i+1}\) (with vertex \(V_{N+1}\) being \(V_1\)).

outputFormat

On the first line, output the highest possible final score.

On the second line, output in increasing order (separated by a single space) all the numbers of the edges which, if removed on the first move, allow one to achieve that highest score.

sample

4
1 2 3 4
+*+*

36
3