TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

7.0% (3/43)

Tags

Description

處理完那群恐怖的女學生之後,妁艷卯足全力,一口氣衝到頂樓,只為了那背影。

呼~呼~呼~。頂樓上空曠的感覺,讓先前在那狹窄樓梯間的壓迫感消失了不少。妁艷喘著氣望向那個人影,發現是一個女學生,和其他學生一樣,她正以呆滯的眼神望著妁艷,而她身旁還站著YOOOOOOOOO!一個蘿莉。

「從樓下看明明只有一個人的說,真是詭異。」妁艷自言自語道:「還有,那個蘿莉到底是敵還是友啊......」

就在妁艷猶豫的時候,妁艷腳下的地板突然炸開。

妁艷連忙跳開。而那個蘿莉已趁機召喚出了N - 1個分身,這N個蘿莉面對妁艷由近到遠排成一排。接著蘿莉們跳到空中,每個人都有自己所在的高度。對於每個蘿莉,如果她後面有蘿莉所在高度比她低,那她們就會一起引爆妁艷腳下的地板一次。

看來是敵人呢。妁艷拿出武器擺好架式。這時妁艷卻發現他仍然無法很自在的使用他的武器,他只會增加射程以及目標物的高度,也就是說妁艷不能先攻擊遠的再攻擊近的、不能先攻擊高再攻擊低的敵人。因此,妁艷可能無法解決所有的蘿莉。

妁艷對於閃躲攻擊不是很在行,因此請告訴妁艷,在他解決掉盡量多的蘿莉後,蘿莉們最少會發動幾次攻擊。

Input Format

第一行有一個正整數N,代表有幾個蘿莉。
第二行有N個正整數,代表由近到遠每個蘿莉的高度。

N ≤ 100,000
蘿莉的高度 ≤ 109

Output Format

一個整數,代表蘿莉們發動攻擊次數的最小值。

Sample Input 1

5
1 2 3 2 1

Sample Output 1

1

Hints

Problem Source

原TIOJ1758 / problem setter : esrever

Subtasks

No. Testdata Range Score
1 0 11
2 1 11
3 2 11
4 3 11
5 4 11
6 5 11
7 6 11
8 7 11
9 8 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9