TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (22/22)

Submission's AC Ratio

56.7% (80/141)

Description

「咚!!」 勇者帥氣地推開大門,準備跟魔王拼命。
正當勇者的劍準備出鞘,勇者定神一看…「咦!怎麼魔王的等級比我高了10倍!」
這完完全全沒有道理,畢竟勇者已經達成所有條件,組成了理論上最強的隊伍了。
「嘖!這遊戲一定不是設計給人過關的!」勇者憤怒道。

不論如何,現在最重要的事情就只有逃命了。

要知道,魔王房間對外的通道只有由$N$根石柱由內往外排成的道路,剩下的地方都被岩漿所包圍。這$N$根石柱的高度都不同,而且對於所有石柱A來說,假設B是A往內走第一個比A高的石柱,C是A往外走第一個比A高的石柱,那麼從石柱A可以跳到B跟C中比較矮的那根柱子(如果B和C都不存在,那麼A不能跳到其它石柱;如果只有B存在,那麼可以從A跳到B;如果只有C存在,那麼可以從A跳到C)。除此之外,如果有一個石柱D比A矮,而且D可以跳到A,那麼A也可以跳到D。

然而只要在逃跑的過程中,某個石柱斷裂,就會掉到岩漿裡面熔化掉了。所以勇者想找出哪個石柱是「最容易被經過」的,也就是說被最多的簡單路徑經過。但魔王就緊追在後,勇者沒什麼時間了,所以請你撰寫一支程式幫忙勇者化解危機。

註:簡單路徑的定義為,從一個柱子開始經過一系列跳躍後到達另一根柱子,且過程中經過的柱子(含起終點)互不相同並至少有兩根。

Input Format

第一行有一個正整數$N\leq 10^ 6$,代表柱子個數。
第二行有$N$個相異正整數$h_1,h_2,\dots,h_N\leq N$,代表柱子由內到外的高度。

子任務(測資) 額外限制 分數
1 (0~4) $n\leq 500$ 28
2 (5~9) $n\leq 10000$ 36
3 (10~14) 無限制 36

Output Format

請輸出一行,包含兩個正整數。第一個正整數代表有幾條簡單路徑通過最容易被經過的柱子,第二個正整數代表最容易被經過的柱子的編號。若有多個答案,輸出編號最小的那個。

Sample Input

5
1 5 2 4 3

Sample Output

18 4

Hints

Problem Source

Problem set / Description by Paupière
題目取自2015 TOI第一階段選訓第三次模擬考pB

Subtasks

No. Testdata Range Score
1 0~4 28
2 5~9 36
3 10~14 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 1
2 1000 131072 262144 1
3 1000 131072 262144 1
4 1000 131072 262144 1
5 1000 131072 262144 2
6 1000 131072 262144 2
7 1000 131072 262144 2
8 1000 131072 262144 2
9 1000 131072 262144 2
10 1000 262144 262144 3
11 1000 262144 262144 3
12 1000 262144 262144 3
13 1000 262144 262144 3
14 1000 262144 262144 3