題目連結：
題目大意：
輸入第一列給定一正整數 n（1 ≦ n ≦ 3 × 10 ^ 5），代表有一數列一開始長度為 n。接著第二列給定 n 個正整數（皆介於 1 ～ 10 ^ 7 之間，且這 n 個數彼此相異）。
假設現在數列的內容為 a1 、 a2 、 …… 、ak（k ≠ 1），則我們需要從中找到數字最小者，以該數為中心將數列分成左右兩邊（注意，作為中心的數不屬於任何一側）。如果左側的總和 > 右側的總和，則數列將被替換為左側的子數列；而當左側總和 ≦ 右側總和，則將原數列替換為右側的子數列。而當有一側為空時，該側之總和為 0。
重複以上步驟直到我們剩下一個數字為止，而該數就是「幸運數字」。試問：輸入給定的數列之「幸運數字」為何？
範例輸入：
範例輸入 #1
6
4 2 1 5 3 7
範例輸入 #2
10
9 8 3 123 4 12 66 99 40 17
範例輸出：
範例輸出 #1
7
範例輸出 #2
99
解題思維：
假設「現在」的數列是原數列第 L ～ R 項（寫作 [L, R]，且以下所有索引值皆從 1 開始），因此可以看到每次的數列替換，我們需要求出 [L, R] 這個區間的最小值。
因為數列每次最差可能只減少一項（即作為中心的數字），所以如果我們使用迴圈去線性地找 [L, R] 之間的最小值，時間複雜度會是 O(n ^ 2)。因此我們需要線段樹（Segment Tree，參見這題）這個資料結構，這樣總體最差就會降低為 O(n log n)。
當我們找到最小值（以及位置 P）之後，我們只需要利用前綴和（Prefix Sums，參見這題）即可求出左右兩側子數列的總和。接著就按照題目要求去更新 [L, R]——即當左側總和 > 右側總和，將 R 之值更新為 P - 1（因為替換成左側）；反之，將 L 更新為 P + 1。
重複以上步驟直到我們得到 L = R。此時數列第 L 項即為所求。
而因為輸入資料量不少，所以建議最佳化一下輸出入之速度（簡單的即可，如這題）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
