@everyone 揪打CF
4455 . 整理河內塔
TopCoder
Tags
Description
身為資奧國手的你，一定聽說過河內塔，他可能在你剛學遞迴的時候把你頭腦的CPU燒到冒煙，或是被你用3秒解決
今天你想要整理散落在世界各地的 $n$ 個河內塔圓盤們，你發現如果不把一個圓盤套到河內塔的柱子上，便會有一股神奇的魔法力量阻止你拿到下一個圓盤
而且因為有人在幫你一起整理，你能拿到的圓盤都是他遞給你的，並且他會順便告訴你這個圓盤的大小 $a_i$ ，也就是說，你不能按照自己的心情決定先拿哪一個
但是由於這個河內塔比較火爆，儘管你只是在整理他，如果你不按照從大到小的順序擺放，他就會再次動用魔法力量把你炸了
喔對 如果你嘗試把一個放下去的圓盤拿起來 大幅增加花費時間 那個幫你整理的人可能不爽你 並同時把所有圓盤丟到你臉上 所以不要這麼做
請你計算一下你總共要用幾根柱子才能把所有的圓盤整理好？
Input Format
$n$ $(1≤n≤2*10 ^ 5)$
$a_1, a_2, ... ,a_n$ $(1≤a_i≤10 ^ 9)$
Output Format
一個非負整數代表你需要用幾根柱子
Sample Input 1
5
3 8 2 1 5
3 8 2 1 5
Sample Output 1
2
Hints
一個圓盤可以放到另外一個圓盤上若且唯若此圓盤的大小嚴格小於底下的圓盤的大小
雖然不知道為什麼河內塔會有兩個一樣大的圓盤就是了
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~19 | 100 |