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): Choose an index (i) ((1 \le i \le n)). Choose a set (S) to be either the prefix (\{1,2,\ldots,i-1\}) or the suffix (\{i+1,i+2,\ldots,n\}). 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. Choose (i = 1) and (S) as the suffix (\{2, 3, 4, 5\}): ((6, 3, 5, 5, 2) \to (6, 9, 7, 7, 10)). Choose (i = 3) and (S) as the prefix (\{1, 2\}): ((6, 9, 7, 7, 10) \to (8, 5, 7, 7, 10)). 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. Choose (i = 2) and (S) as the suffix (\{3\}): ((2, 1, 100000) \to (2, 1, -99998)). Choose (i = 1) and (S) as the suffix (\{2, 3\}): ((2, 1, -99998) \to (2, 3, 100002)). Note that the sequence may cont