a139. B. 島嶼

Content

隨著全球暖化，海平面不斷的上漲，導致了部分的陸地淹沒成為了島嶼。陸地是一維直線上的 $n$ 個區塊，第 $i$ 個區塊的高度是 $A_i (1 ≤ i ≤ n)$。定義一座島嶼是一段連續的陸地區塊，且每一塊的高度 $\{A_x, A_{x+1}, \dots , A_{y-1}, A_y\}$ 皆大於海平面高度。

現在海平面由高度 $0$ 逐漸的上漲到高度無限大，過程中有些陸地被淹沒變成數塊島嶼，有時候則是整座島嶼完全沉入海中。請問在海水上漲過程中，最多能同時存在幾座島嶼。

Input

輸入的第一行包含一個數字 $n$，代表陸地的數量。
接下來下一行有 $n$ 個數，第 $i$ 個數 $A_i$ 代表第 $i$ 塊陸地的高度。

$1 ≤ n ≤ 10^5$
$0 ≤ A_i ≤ 10^9$

Output

請輸出上漲過程中最多能同時存在幾座島嶼。至少存在一個陸地高度大於 0。

Sample Input #1

6
0 1 2 1 3 2

Sample Output #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 0.5s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1M
公開測資點#3 (5%): 0.5s , <1M
公開測資點#4 (5%): 0.5s , <1M
公開測資點#5 (5%): 0.5s , <1M
公開測資點#6 (5%): 0.5s , <1M
公開測資點#7 (5%): 0.5s , <1M
公開測資點#8 (5%): 0.5s , <1M
公開測資點#9 (5%): 0.5s , <1M
公開測資點#10 (5%): 0.5s , <1M
公開測資點#11 (5%): 0.5s , <1M
公開測資點#12 (5%): 0.5s , <1M
公開測資點#13 (5%): 0.5s , <1M
公開測資點#14 (5%): 0.5s , <1M
公開測資點#15 (5%): 0.5s , <1M
公開測資點#16 (5%): 0.5s , <1M
公開測資點#17 (5%): 0.5s , <1M
公開測資點#18 (5%): 0.5s , <1M
公開測資點#19 (5%): 0.5s , <1M

Hint ：

(10%) $1 ≤ n ≤ 10$, $0 ≤ A_i ≤ 10$, 陸地高度皆相異。
(20%) $1 ≤ n ≤ 1000$, 陸地高度皆相異。
(30%) 陸地高度皆相異。
(40%) 無特殊限制

Tags:

出處:

2022 資訊之芽算法班入芽考 [管理者： ktlai (K．我已霸榜．Tlai) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」