(*

Polygon (IOI 1998)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA



Utilizziamo la programmazione dinamica per calcolare i massimi e minimi
valori ottenibili con una sottoespressione che coinvolge i vertici a partire
dal vertice j. Per fare cio` basta utilizzare i valori estremali delle
possibili coppie di sottoespressioni di lunghezza k e i-k che partono dal
vertice j e dal vertice j+k, rispettivamente.

E` necessario calcolare i massimi e i minimi perche' per massimizzare un
prodotto bisogna considerare il caso che un fattore sia negativo.

*)

Program Polygon;


function max(a,b: LongInt): LongInt;
BEGIN
	if a<b then max := b else max := a;
END;

function min(a,b: LongInt): LongInt;
BEGIN
	if b<a then min := b else min := a;
END;

CONST MAXN = 50;     (* Massimo numero di vertici. *)

var
	op: array [0..MAXN-1] of Char;
		(* Operatore che compare _prima_ del vertice corrispondente. *)
	nv:  array [0..MAXN-1] of Integer; (* Intero sul vertice *)
	massval: array [0..MAXN-1] of array [0..MAXN-1] of LongInt;
		(* Matrice da riempire dinamicamente: il primo indice e` la lunghezza
			della sottoespressione da massimizzare, il secondo il vertice da cui
			parte l'espressione. *)
	minval: array [0..MAXN-1] of array [0..MAXN-1] of LongInt;
		(* Come sopra per i minimi. *)
	tempn: array [0..MAXN-1] of Integer;
	tempop: array [0..MAXN-1] of Char;
		(* In queste matrici ricopieremo op e n a meno del primo lato eliminato
			e di rotazioni cicliche. *)
	M: array [0..MAXN-1] of LongInt;
		(* Massimo ottenibile rimuovendo inizialmente un certo lato. *)

	i, j, k, l, N: Integer;
	p, tmax, tmin, ottimo: LongInt;
	t: Boolean;
	spazio: Char;

BEGIN
	READLN(N);
	FOR i:=0 TO N-1 DO
	BEGIN
		IF i=N-1 THEN READ(op[i], nv[i])
		ELSE READ(op[i], nv[i], spazio);
		if op[i] = 't' THEN op[i] := '+' ELSE op[i] := '*';
			(* Usiamo una notazione piu` umana. *)
	END;

	ottimo := Low(ottimo); (* Si parte da -oo *)

	FOR l:=0 TO N-1 DO (* l e` il lato da eliminare *)
   BEGIN
		FOR i:=0 TO N-1 DO (* Ricopiamo n in tempn e op in tempop a partire da
                             l ciclicamente fino a l-1. *)
		BEGIN
			tempn[i] := nv[(i+l) MOD N];
			tempop[i] := op[(i+l) MOD N];
		END;

	(* I valori massimi e minimi per le sottoespressioni di lunghezza 1 sono
		gli elementi di tempn. *)

		FOR i:=0 TO N-1 DO
		BEGIN
			massval[1][i] := tempn[i];
			minval[1][i] := tempn[i];
		END;

		FOR i:=2 TO N DO	(* i scorre la dimensione corrente di
									una sottoespressione. *)
		BEGIN
			FOR j:=0 TO N-i DO	(* j scorre la posizione da cui calcoliamo i
											valori estremali di una sottoespressione di
											lunghezza i. *)
			BEGIN
				tmax := Low(tmax);
				tmin := High(tmin);

				FOR k:=1 TO i-1 DO	(* k scorre gli spezzamenti possibili per
												un'espressione lunga j. *)
					IF tempop[j+k] = '+' THEN
					BEGIN
						tmin := min(tmin, minval[k][j] + minval[i-k][j+k]);
						tmax := max(tmax, massval[k][j] + massval[i-k][j+k]);
					END
               ELSE	(* Massimizzare e minizzare un prodotto e` solo un po'
								piu` complicato che farlo per una somma! *)
					BEGIN
						tmax := max(tmax,
										max(massval[k][j] * massval[i-k][j+k],
										max(massval[k][j] * minval[i-k][j+k],
										max(minval[k][j] * massval[i-k][j+k],
										minval[k][j] * minval[i-k][j+k]))));
						tmin := min(tmin,
										min(massval[k][j] * massval[i-k][j+k],
										min(massval[k][j] * minval[i-k][j+k],
										min(minval[k][j] * massval[i-k][j+k],
										minval[k][j] * minval[i-k][j+k]))));
					END;
				(* A questo punto tmax e tmin contengono il massimo e il minimo
					valore ottenibile con una sottoespressione di lunghezza i
					costruita a partire dal vertice j. *)
				massval[i][j] := tmax;
				minval[i][j] := tmin;
			END;
      END;

	(* massval[N][0] ora contiene il massimo valore di un'espressione di
		lunghezza N ottenuta a partire da 0, cioe` il massimo valore di
		un'espressione che utilizza tutti i vertici. Dobbiamo pero`
		massimizzare anche rispetto alla scelta di l. *)

		M[l] := massval[N][0];
		ottimo := max(ottimo, M[l]);
   END;

	WRITELN(ottimo);

	(* Stampiamo ora i valori di i per cui la cancellazione dell'i-esimo lato
		ha dato origine a un risultato ottimo. ATTENZIONE: l'indicizzazione
		e` a partire da uno! *)
	FOR i:=0 TO N-1 DO
		IF M[i] = ottimo THEN
		BEGIN
			IF t THEN WRITE(' ');
			WRITE(i+1);
			t := true;
		END;

	WRITELN;
END.