No tag edit access

E. Fedya the Potter

time limit per test

2.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFedya loves problems involving data structures. Especially ones about different queries on subsegments. Fedya had a nice array $$$a_1, a_2, \ldots a_n$$$ and a beautiful data structure. This data structure, given $$$l$$$ and $$$r$$$, $$$1 \le l \le r \le 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} + \ldots + b_r$$$ for given $$$l$$$ and $$$r$$$, $$$1 \le l \le r \le 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 $$$\lfloor \frac{k + 1}{2} \rfloor$$$, 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 \le n \le 50\,000$$$).

Second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — elements of the array ($$$1 \le a_i \le 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$$$.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/18/2019 09:45:02 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|