TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

61.1% (11/18)

Tags

Description

資訊圈一直以來流傳著一道怪題目,題序如下:

給你n條線段,每條線段給你以x座標左端點與右端點來表示。請問哪一個x座標上面有最多條線段通過,以及這個通過的數量是多少?


身為建電最強學術的阿蘇,當然也花費了很多時間在這題上面。

有一天,阿蘇突然想到,如果把端點做了一些排序之類的操作,他就可以將此問題的複雜度從$O(n^2)$壓到$O(n)$。他將此做法發表在國際知名期刊上,獲得的全世界資訊競賽圈的肯定。

這就是鼎鼎大名的線段蘇優化的由來。

成功獲得國際聲望的阿蘇自己便自己跑去ACM領獎了,留下AaW一個人在空無一人的社辦裡面,孤獨的亂掰著小社賽的題序。

望著空空如也的社辦,AaW坐在沙發上發愣著。

千里孤墳,無處話淒涼

塵滿面,鬢如霜。

想到自己還是進不了間中校隊,AaW不禁流下了一滴滴眼淚。

最近AaW的心情真的很不穩定,常常陷入如雲霄飛車般的起伏當中,具體一點的話,他的心情起伏大概跟底下這張圖一樣,呈現直角形的曲線:


眼淚順著AaW的臉龐留下,滑入了他的嘴角中,一股鹹味湧上舌尖,AaW心頭一震......

這...這是..Brine!!!

全拆國低中的偶像突然地出現在AaW的面前,令AaW大感震驚。

「你...為什麼會出現?」\\

Brine不回答,靜靜的流向剛剛的AaW畫的那張圖中。

只見那張圖的下半部慢慢的被鹽水淹沒,留下了一座座島嶼。


「這...這是......完美的資訊問題!!!」AaW立馬看出這是一題成功解出後就可以超越阿蘇成就的絕佳問題。

於是,AaW想請問你,如果Brine可以自由決定他要淹水的高度,那麼最多AaW的心情圖中可以留下幾座島嶼?

喔對了,如果有一處的地形高度和水位高度一致,則此處仍視為被水面淹過。

Input Format

第一行給個正整數n,代表此圖表橫向總共可以被切成n塊寬度一致的矩形。

第二行有$n$個正整數,給一個高度$h_i$,代表第i塊矩形的高度。

$1 \le n \le 10^6, 1 \le h_i \le 10^9$

Output Format

請輸出一個正整數,代表在可以任意調整水位高度時,最多可以留下幾座島嶼?

順帶一提的是,因為$h_i \ge 1$,所以當水位高度為0時,全部算是1座島嶼。

Sample Input 1

5
5 1 5 1 5

Sample Output 1

3

Sample Input 2

5
1 5 3 5 1

Sample Output 2

2

Sample Input 3

8
1 3 4 2 4 1 3 1

Sample Output 3

3

Sample Input 4

7
1 2 3 4 5 6 7

Sample Output 4

1

Hints


以上圖這樣為例,是3個島嶼


以上圖這樣為例,是4個島嶼

可以發覺的是,這條曲線最多就只能產生4個島嶼

話說,這題和線段蘇有關聯喔...

Problem Source

111年小社賽pE

Subtasks

No. Testdata Range Constraints Score
1 0~13 $1 \le n \le 100, 1 \le h_i \le 100$ 50
2 0~23 $1 \le n \le 1000000 , 1 \le h_i \le 1000000000 \, $ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536 1 2
1 1000 250000 250000 65536 1 2
2 1000 250000 250000 65536 1 2
3 1000 250000 250000 65536 1 2
4 1000 250000 250000 65536 1 2
5 1000 250000 250000 65536 1 2
6 1000 250000 250000 65536 1 2
7 1000 250000 250000 65536 1 2
8 1000 250000 250000 65536 1 2
9 1000 250000 250000 65536 1 2
10 1000 250000 250000 65536 1 2
11 1000 250000 250000 65536 1 2
12 1000 250000 250000 65536 1 2
13 1000 250000 250000 65536 1 2
14 1000 250000 250000 65536 2
15 1000 250000 250000 65536 2
16 1000 250000 250000 65536 2
17 1000 250000 250000 65536 2
18 1000 250000 250000 65536 2
19 1000 250000 250000 65536 2
20 1000 250000 250000 65536 2
21 1000 250000 250000 65536 2
22 1000 250000 250000 65536 2
23 1000 250000 250000 65536 2