0 Judge
Code: 0
傳說中$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