TopCoder

Thumb a
$ $
$ \color{red}{\href{../users/icube}{\circ Inactive}} $

User's AC Ratio

100.0% (17/17)

Submission's AC Ratio

66.7% (28/42)

Tags

Description

ABCLS Contest, Problem Set (Printable Version, PDF Document)

還記得甦蹦嗎?沒錯,還是那隻愛吃橘子的烏龜(*)。
話說甦蹦歷經了21年總算找到了傳說中的橘子的種子;也發現了神秘培植法──烏拉拉嘎嚕嚕嘎烏。
在你幫他分析過栽種的經濟效益後他決定開始栽種傳說中的橘子了!

但是甦蹦十分小心謹慎:已經砸了21年青春在傳說中的橘子上面了,如今真的要栽種了當然不能容許一點差池。
所以甦蹦決定要架設一條長形的籬笆把他的橘子園跟INF聚落隔離。

於是甦蹦對著橘子園的邊界進行研究:既然是在INF聚落嘛,橘子園的邊界自然也可以用一條數線表示,
只能在整數點的位置打樁、且在每個位置打樁有著不同的代價。

甦蹦把橘子園邊界的數線給了DBTF看。他們兩個分別回家草擬了籬笆結構圖,也就是要在哪些位置打樁。
第二天他們兩個人交換彼此的設計圖,發現了幾個巧合:

  1. 他們打樁的數量相等、總代價也相等,但方案不完全相同!
  2. 他們分別把代價依照位置排序好後形成的序列竟然長得一模一樣!
  3. 不僅如此,他們打樁位置的個數是所有符合上述條件中最多的!

你聽聞有此事覺得很有趣,便偷偷探勘了橘子園邊界,想算出甦蹦的籬笆總共打了幾個樁。

Input Format

第一行有一個正整數N,表示總共有N個位置可以打樁。
第二行有N個正整數,依序表示位置從小到大每個位置打樁的代價Ki。

對於所有測試測資,N ≤ 100,000、1 ≤ Ki ≤ 1,000,000,000。

Output Format

輸出只有一行包含一個整數M,表示甦蹦的籬笆總共打了M個樁。

Sample Input

5
1 5 3 5 4

Sample Output

3

Hints

範例測資中,如果甦蹦選了1 5 3 5 4、DBTF選了1 5 3 5 4,(劃底線表示選)
那麼雖然他們選的木樁不完全一樣,可是依照位置排序後代價都是1 5 4。

(*)詳情見建國中學2010年校內模擬賽Contest add prob 2 / Contest 7 prob 3 / Contest 9 prob 3

Problem Source

原TIOJ1691 / ABCLS Contest, Problem A

Subtasks

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB)
0 2000 65536
1 2000 65536
2 2000 65536
3 2000 65536
4 2000 65536
5 2000 65536