Fedya the Potter

Fedya loves problems involving data structures. Especially ones about different queries on subsegments. Fedya had a nice array a_1, a_2, … a_n and a beautiful data structure. This data structure, given l and r, 1 ≤ l ≤ r ≤ n, could find the greatest integer d, such that d divides each of a_l, a_{l+1}, ..., a_{r}.

Fedya really likes this data structure, so he applied it to every non-empty contiguous subarray of array a, put all answers into the array and sorted it. He called this array b. It's easy to see that array b contains n(n+1)/2 elements.

After that, Fedya implemented another cool data structure, that allowed him to find sum b_l + b_{l+1} + … + b_r for given l and r, 1 ≤ l ≤ r ≤ n(n+1)/2. Surely, Fedya applied this data structure to every contiguous subarray of array b, called the result c and sorted it. Help Fedya find the lower median of array c.

Recall that for a sorted array of length k the lower median is an element at position ⌊ (k + 1)/(2) ⌋, if elements of the array are enumerated starting from 1. For example, the lower median of array (1, 1, 2, 3, 6) is 2, and the lower median of (0, 17, 23, 96) is 17.

Input

First line contains a single integer n — number of elements in array a (1 ≤ n ≤ 50 000).

Second line contains n integers a_1, a_2, …, a_n — elements of the array (1 ≤ a_i ≤ 100 000).

Output

Print a single integer — the lower median of array c.

Examples

Input

2 6 3

Output

6

Input

2 8 8

Output

8

Input

5 19 16 2 12 15

Output

12

Note

In the first sample array b is equal to {3, 3, 6}, then array c is equal to {3, 3, 6, 6, 9, 12}, so the lower median is 6.

In the second sample b is {8, 8, 8}, c is {8, 8, 8, 16, 16, 24}, so the lower median is 8.

inputFormat

Input

First line contains a single integer n — number of elements in array a (1 ≤ n ≤ 50 000).

Second line contains n integers a_1, a_2, …, a_n — elements of the array (1 ≤ a_i ≤ 100 000).

outputFormat

Output

Print a single integer — the lower median of array c.

Examples

Input

2 6 3

Output

6

Input

2 8 8

Output

8

Input

5 19 16 2 12 15

Output

12

Note

In the first sample array b is equal to {3, 3, 6}, then array c is equal to {3, 3, 6, 6, 9, 12}, so the lower median is 6.

In the second sample b is {8, 8, 8}, c is {8, 8, 8, 16, 16, 24}, so the lower median is 8.

样例

2
6 3

                                                               6

</p>