Finále

B: Opět halda sněhu

Abys mohl odevzdávat úlohy, musíš se přihlásit nebo zaregistrovat

Nejsi finalista, takže se neobjevíš ve výsledcích.

Zadání (Řešení)

Sotva technické služby svezly sníh z ulic na náměstí a vytvořily tam haldu sněhu, už dostaly další úkol. Nějaký umělec nabídl městu, že z toho sněhu udělá sochu. Na to ale potřebuje mít co největší rovný kvádr, který pak může začít opracovávat. S jakým největším může počítat?

Halda sněhu vypadá naprosto stejně jako v domácím kole. Stačí nám její průřez, ten si můžeme nakreslit na čtverečkovaný papír. Na vstupu máte výšky souvislých vrstev sněhu na každém sloupečku hromady. Nejsou tam tedy žádné díry a mezi sloupečky nejsou žádné mezery. Sníh netaje ani nijak neubývá.

Vypište obsah největšího souvislého obdélníku, který se nachází uprostřed hromady a je tvořen sněhem.

Tvar vstupu

Na prvním řádku vstupního souboru máte číslo T, počet testovacích vstupů v souboru.

Každý vstup vypadá tak, že na prvním řádku máte číslo N, a na druhém řádku N čísel. Když budete průřez hromady číst po řádcích zleva, pak první číslo znamená výšku sněhu na prvním políčku. Druhé číslo je výška sněhu na druhém políčku, a obecně i-té číslo znamená výšku sněhu v i-tém sloupečku.

Tvar výstupu

Do výstupního souboru vypište na j-tý řádek výstup j-tého vstupu. Výstupem nechť je jedno celé číslo, obsah největšího souvislého obdélníku sněhu, který je v hromadě.

Lehká verze

  • T ≤ 10
  • N ≤ 1 000
  • 0 ≤ výšky sněhu ≤ 1 000

Těžká verze

  • T ≤ 10
  • N ≤ 1 000 000
  • 0 ≤ výšky sněhu ≤ 10 000 000

Ukázkový vstup

2
7
3 6 7 4 2 3 1
9
3 7 6 8 4 5 2 8 7

Ukázkový výstup

12
20

Druhá hromada s největším obdélníkem je zde na obrázku:

Máš na to!

I ty můžeš vyhrát! Nebo to aspoň zkusit :)