N3 - Násobenie 3

Časový limit: 30s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

Paulínka sa na hodine matematiky nudí (teraz preberajú násobenie čísel, ktoré už dávno vie). Keďže má so sebou hracie karty s číselnými hodnotami, rozhodla si zahrať hru, kde z balíčka kariet bude brať karty postupne z jedného z koncov. Hodnotu karty vynásobí počtom kariet, ktoré už z balíčka zobrala. Po pár hrách už začala premýšľať, v akom poradí má jednotlivé karty brať, aby na konci získala najväčší súčet takto vzniknutých súčinov.
Pomôžte jej napísať program, ktorý pre zadané poradie kariet v balíčku, nájde najlepšie možné riešenie.

Vstup N3

Prvý riadok vstupu obsahuje počet testovacích sád. Každá testovacia sada pozostáva z dvoch riadkov: Prvý riadok obsahuje jedno celé číslo N (1 ≤ N ≤ 2 000) – počet kariet. Druhý riadok obsahuje N celých čísel oddelených medzerami, hodnoty i-tej karty h_i (1 ≤ h_i ≤ 1 000) .

Výstup N3

Výstupom je jeden riadok pre každú testovaciu sadu obsahujúci N znakov < (ľavý kraj) > (pravý kraj) určujúce poradie výberu kariet z krajov pre dosiahnutie najvyššieho výsledku. Ak je takýchto riešení viacero, vypíšte ľubovoľné z nich.

Príklad

Vstup:

1
5
1 3 1 5 2

Výstup:

<><<>

Poznámka

Karty v príklade sú zobrazené na obrázku (1-3-1-5-2). Pri výbere kariet z krajov podľa poradia <><<>, teda karty v poradí s hodnotami 1, 2, 3, 1, 5 dostávame súčiny 1, 4, 9, 4, 25 s celkovým súčtom 43.

21 Domáce 2