TopCoder

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

User's AC Ratio

87.5% (14/16)

Submission's AC Ratio

30.4% (31/102)

Tags

Description

「沒想到你就是那傳聞中擁有無限多間房間的希爾伯特啊!」兩人邊在暴風雨中小心翼翼又快速地前進,小向邊驚訝道。
「唉呀,我怎麼變那麼有名啦。」
「難怪在這暴風雨中你的旅館還有空位。」
「話別說的那麼簡單。你知道你一個人入住就要讓無限多個人搬家嗎?要不是看在剛剛你巧妙地解開了我的謎題,我可不想幹這種麻煩事。」話中夾雜了些許的抱怨口氣。
「也對……真是不好意思,辛苦你了。」小向帶著一點歉意答話。
「啊…其實也沒什麼啦。這個壞天氣…相信大家都會體諒的。」

說著說著,兩人走到了旅館。當然,希爾伯特成功地「挪」出了空房給小向。

「好好休息吧。然後……看看天氣轉晴之後…怎麼說呢…」
「?」
「我或許可以教你一些『把戲』。」
身為見習魔法少女,小向當然是能學則學。開心地答應了之後小向就回到了他的房間。

「!!!」地面突然開始搖晃,在暴風雨終於減弱的半夜裡睡著正香甜的小向被驚醒。衝出門外的小向發現她住的$N$號房以前的$N$個房間(編號0到$N-1$)的位置已被重新排列。「轟!」編號0到$N-2$的房間突然間各伸出一個橋,「咚!」地接到了編號1到$N-1$的某個房間。這種能操控大地的魔法到底是哪個大魔法師使出來的…儘管這是小向第一個想法,但是眼前的慘況可不容許她把腦子用在其它地方。想到了希爾伯特也住在裡面的某間房間的她,第一個想法就是儘快衝過去找希爾伯特。

冷靜下來以後,小向仔細觀察了目前的情勢。編號0到$N-1$的房間位置已被重排,由左而右的房間編號分別是$a_0,a_1,\dots,a_{N-1}$。而對於第$i$個位置,編號$a_i<N-1$的房間,如果在他左(右)側編號比他大的房子有$L(R)$棟且編號由小排到大是$b_0,b_1,\dots,b_{L-1}(c_0,c_1,\dots,c_{R-1})$,那麼他所伸出的橋梁連結的房間的編號就是$\min(b_{(L-1)/2},c_{(R-1)/2})$(這裡的除法無條件捨去,且如果$L(R)=0$,那麼$b_{(L-1)/2}(c_{(R-1)/2})=\infty$)。然而知道這些並沒有任何幫助。

「小向,聽得見嗎?」突然聲音在小向腦袋裡迴蕩。這是被稱為「念話」的一種魔法,能透由心念和其它人溝通。
「我是希爾伯特,我被困在房間裡了。雖然我不太清楚我在哪間房間裡,不過我可以確定我的房間周圍的橋梁不會比其它任何一間房間少。快…」

聲音就中止了。
「可惡…要是我的瞬間移動只要指定『人』而不用指定『目的地』就好了…」小向氣憤道。
不過,當務之急即是找到希爾伯特的所在地並瞬間移動過去。

Input Format

第一行有一個正整數$2\leq N\leq 10^ 6$,代表被重排的房間個數。
之後一行有相異的$N$個整數$0\leq a_i<N$,代表重排後房間由左至右的編號。

子任務(測資) 額外限制 分數
1 (0~2) 房間沒有被重排 8
2 (3~7) $N\leq 10^ 4$ 16
3 (8~12) $N\leq 10^ 5$ 32
4 (13~17) 44

Output Format

輸出一個正整數,代表房間周圍的橋梁數的最大值。

Sample Input

5
0 3 2 4 1

Sample Output

3

Hints

編號0的房間伸出的橋梁連結到了編號$\min(\infty, 2)=2$的房間。
編號1的房間伸出的橋梁連結到了編號$\min(3, \infty)=3$的房間。
編號2的房間伸出的橋梁連結到了編號$\min(3, 4)=3$的房間。
編號3的房間伸出的橋梁連結到了編號$\min(\infty, 4)=4$的房間。
編號4的房間沒有伸出橋梁。
因此編號0的房間周圍有1座橋梁,編號1的房間周圍有1座橋梁,編號2的房間周圍有2座橋梁,編號3的房間周圍有3座橋梁,編號4的房間周圍有1座橋梁。

Problem Source

Problem Set / Description by Paupière

Subtasks

For Testdata: 0 ~ 2, Score: 8
For Testdata: 3 ~ 7, Score: 16
For Testdata: 8 ~ 12, Score: 32
For Testdata: 13 ~ 17, Score: 44
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1500 262144 262144
1 1500 262144 262144
2 1500 262144 262144
3 1500 262144 262144
4 1500 262144 262144
5 1500 262144 262144
6 1500 262144 262144
7 1500 262144 262144
8 1500 262144 262144
9 1500 262144 262144
10 1500 262144 262144
11 1500 262144 262144
12 1500 262144 262144
13 1500 262144 262144
14 1500 262144 262144
15 1500 262144 262144
16 1500 262144 262144
17 1500 262144 262144