TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (26/26)

Submission's AC Ratio

69.6% (39/56)

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 1

5
1 5 3 5 4

Sample Output 1

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

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

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