$M$的藏寶室

題目敘述

傳說中$S$地區在很久之前有一個精明的國王$M$，擁有超人的智慧，大量的財富和無上的權力。但是由於$M$的罪過使得他的王國在他兒子那一代發生分裂，$M$大量的財富消失的無影無蹤。傳說在$M$還在位時，就已經料到他的王國會發生分裂，因此就事先把財寶藏在$S$地區的某個地方。

在偶然的機會下，卦長在古籍裡讀到了這麼一段話："此時，我正在$SB$女王雙乳峰南峰北面的一個無雪的小山洞裡，饑餓難捱，奄奄一息。現在是1590年，我以碎骨為筆，鮮血為墨，在衣服碎布上寫下這封信。如果我的僕人能發現的話，會將它帶回$P$國，讓我的朋友（此處字跡模糊難辨）交給國王。國王也許會派一支軍隊前來。如果軍隊能活著穿過沙漠和高山，戰勝強悍的$MM$人，破解他們的巫術，那麼，他就能成為自$M$之後世上最最富有的國王。在白色的$SM$像後面，我親眼看見了$M$的密室，裡面堆放著無數的鑽石..."

看到這段敘述，讓卦長覺得興奮難耐，他決定帶著他的探測器去$S$地區尋找$M$的寶藏，他很順利地來到$SB$女王雙乳峰，以高強的武藝打敗了$MM$人，並且在山頂附近找到了白色$SM$雕像。可是在雕像的後面是很多個山洞，每個山洞中都是一個巨大的迷宮，裡面有很多機關，惟又找到破解機關的方法才能進入迷宮。幸好卦長有帶著探測儀，可以利用它知道山洞中的情況，經過他的探測，山洞的地板都是平的，探測器可以把山洞按深度分成$n$個空間，每個空間都有自己的高度，大小不一，接器會顯示山洞的平面圖。因為當時的人喜歡把機關統一集中在最大的矩形裡面，所以整個平面圖中最大的矩形就是機關室，最大的矩形可能會有很多個，但是機關室只會有一個。由於沒辦法知道寶藏到底在哪個山洞，所以只能用暴力的方式一個一個找，但是卦長自己不太知道要怎麼去尋找機關室，所以就把這個任務交給身為隨從的你。

請你幫忙卦長，找出平面圖中機關室的面積吧！

輸入說明

輸入有多比，每比資料第一行有一個數字$n, \; 1 \leq n \leq 10^5$，表示山洞被探測器分成的空間個數，第二行會有$n$個非負整數(int)以空白隔開，表示每個空間的高度。

輸出說明

對於每個山洞，輸出機關室的面積(可以是0)。

範例輸入

5
1 5 3 3 4
3
100 1 100

範例輸出

12
100

配分方法

• 10% 範例測資
• 20% $n \leq 100$
• 30% $n \leq 1000$
• 40% $n \leq 100000$

Hints

備註

Judge Setting