CF2206H Reflect Sort

You have a sequence of $ n $ integers $ (a_1, a_2, \ldots, a_n) $ , the initial values of which are given to you. You may apply the following operation to the sequence any number of times (possibly zero): 1. Choose an index $ i $ ( $ 1 \le i \le n $ ). 2. Choose a set $ S $ to be either the prefix $ \{1,2,\ldots,i-1\} $ or the suffix $ \{i+1,i+2,\ldots,n\} $ . 3. For every $ j \in S $ , replace $ a_j $ with $ 2a_i - a_j $ . Your goal is to make the sequence non-decreasing and all elements positive, while minimizing $ a_n $ , using the operation above any number of times. That is, $ 1 \le a_1 \le a_2 \le \ldots \le a_n $ must hold in the resulting sequence. What is the minimum possible value of $ a_n $ in the resulting sequence?

The first line of input contains a single integer $ n $ ( $ 2 \le n \le 100\,000 $ ). The second line contains $ n $ integers representing the initial values of $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ).

Output the minimum possible value of $ a_n $ in the resulting sequence.

Explanation for the sample input/output #1 You can do the following sequence of operations. 1. Choose $ i = 1 $ and $ S $ as the suffix $ \{2, 3, 4, 5\} $ : $ (6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10) $ . 2. Choose $ i = 3 $ and $ S $ as the prefix $ \{1, 2\} $ : $ (6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10) $ . 3. Choose $ i = 2 $ and $ S $ as the prefix $ \{1\} $ : $ (8, 5, 7, 7, 10) \to (2, 5, 7, 7, 10) $ . After these operations, the sequence is non-decreasing and all elements are positive. It can be shown that $ a_5=10 $ is the minimum possible value. Explanation for the sample input/output #2 The minimum possible value of $ a_3 $ is $ 100002 $ , which can be attained by the following operations. 1. Choose $ i = 2 $ and $ S $ as the suffix $ \{3\} $ : $ (2, 1, 100000) \to (2, 1, -99998) $ . 2. Choose $ i = 1 $ and $ S $ as the suffix $ \{2, 3\} $ : $ (2, 1, -99998) \to (2, 3, 100002) $ . Note that the sequence may contain non-positive values during operations.