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)
0 1500 262144
1 1500 262144
2 1500 262144
3 1500 262144
4 1500 262144
5 1500 262144
6 1500 262144
7 1500 262144
8 1500 262144
9 1500 262144
10 1500 262144
11 1500 262144
12 1500 262144
13 1500 262144
14 1500 262144
15 1500 262144
16 1500 262144
17 1500 262144