g277.
3. 幸運數字
Content
在 $n$ 個人之中，每個人被分配到一個號碼，記錄為 $a_1, a_2, \dots, a_n$，這些號碼彼此都不相同，我們要找出當中最幸運的一個
已知在$[L, R]$ 區間之中，最幸運號碼定義為：
- 當 $L = R$ 時，幸運號碼為 $a[L]$
- 當 $L < R$ 時，找出當中最小號碼的位置 $m$，並以最小號碼所在的位置將整個區間區分為左邊 $[L, m-1]$與右邊 $[m+1, R]$，計算兩個區間各自的總和，總和比較大的區間即為幸運號碼所在的區間；如果兩個區間的總和相等，則幸運號碼位在右邊的區間，若區間不包含任何數字，總和視為 $0$
重複以上步驟直到收斂至1. 時即可找到幸運號碼
請找出這 $n$ 個人之中的幸運號碼
Input
第一行輸入一個正整數 $n (1 \leq n \leq 3\times 10^5)$，接下來有 $n$ 個數字 $a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^7)$
配分
- (50%) $1\leq a_i \leq n$，所有數字都介於 $1 \sim n$
- (50%) 無其他限制
Output
輸出這 $n$ 個數字中的幸運數字數值
Sample Input
#1
5 4 2 3 1 5
Sample Output
#1
4
Sample Input
#2
8 3 9 4 5 1 6 2 8
Sample Output
#2
9
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 0.5s , <10M
公開 測資點#1 (5%): 0.5s , <10M
公開 測資點#2 (5%): 0.5s , <10M
公開 測資點#3 (5%): 0.5s , <10M
公開 測資點#4 (5%): 0.5s , <10M
公開 測資點#5 (5%): 0.5s , <10M
公開 測資點#6 (5%): 0.5s , <10M
公開 測資點#7 (5%): 0.5s , <10M
公開 測資點#8 (5%): 0.5s , <10M
公開 測資點#9 (5%): 0.5s , <10M
公開 測資點#10 (5%): 0.5s , <10M
公開 測資點#11 (5%): 0.5s , <10M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
公開 測資點#0 (5%): 0.5s , <10M
公開 測資點#1 (5%): 0.5s , <10M
公開 測資點#2 (5%): 0.5s , <10M
公開 測資點#3 (5%): 0.5s , <10M
公開 測資點#4 (5%): 0.5s , <10M
公開 測資點#5 (5%): 0.5s , <10M
公開 測資點#6 (5%): 0.5s , <10M
公開 測資點#7 (5%): 0.5s , <10M
公開 測資點#8 (5%): 0.5s , <10M
公開 測資點#9 (5%): 0.5s , <10M
公開 測資點#10 (5%): 0.5s , <10M
公開 測資點#11 (5%): 0.5s , <10M
公開 測資點#12 (5%): 0.5s , <10M
公開 測資點#13 (5%): 0.5s , <10M
公開 測資點#14 (5%): 0.5s , <10M
公開 測資點#15 (5%): 0.5s , <10M
公開 測資點#16 (5%): 0.5s , <10M
公開 測資點#17 (5%): 0.5s , <10M
公開 測資點#18 (5%): 0.5s , <10M
公開 測資點#19 (5%): 0.5s , <10M
Hint ：
| ID | User | Problem | Subject | Hit | Post Date |
| 41237 |
|
g277 | 403 | 2024-07-13 17:11 | |
| 40454 |
|
g277 | 348 | 2024-05-21 20:17 | |
| 34494 |
|
g277 | 1109 | 2023-03-26 12:34 | |
| 33652 |
|
g277 | 1182 | 2023-01-18 14:59 | |
| 31815 |
|
g277 | 839 | 2022-08-21 12:00 |