You are driving your car to Southern France, and you know that you will encounter $$n$$ hitchhikers along the way. Because you would rather have some company on this long and boring trip, you decide to take one of these hitchhikers with you. As the choice is completely yours, you prefer to take the most handsome (or the most sympathetic, the smartest, the richest, …). Since turning back is no option, for each of the hitchhikers you meet you will have to decide immediately whether you will take him or her, or test your luck hoping that you'll meet a more handsome hitchhiker further down the road.

lifter
A typical hitchhiker's gesture.

You choose the following strategy before leaving home, in order to maximize your chance for picking the most handsome hitchhiker. Each time you encounter a hitchhiker, you immediately rate him or her with a score $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) that indicates how handsome the hitchhiker is. The higher the score, the more handsome the hitchhiker.

You skip the first $$n / 2$$ (integer division) hitchhikers, but you remember the highest score that you assigned to each of these hitchhikers. Then you stop for the first hitchhiker that is given a higher score than the highest score from the first $$n / 2$$ hitchhikers. You stop for the last hitchhiker, if you hadn't stopped for any of the other hitchhikers before.

Note

It is easy to see that the above strategy yields at least 25% chance of picking the most handsome hitchhiker. The latter will be the case if the second most handsome hitchhiker is among the first half of the hitchhikers, and the most handsome hitchhiker is in the second half.

This can even be improved slightly to $$1/e = 0.36788$$ by using essentially the same strategy, but evaluating the first $$n / e$$ hitchhikers before starting to decide whether you'll take one of the following hitchhikers.

Input

The first line of the input contains an integer $$n \in \mathbb{N}_0$$ that indicates the number of hitchhikers. This is followed by the scores $$s \in \mathbb{R}$$ ($$0 \leq s \leq 1$$) assigned to the $$n$$ hitchhikers, each on a separate line.

Output

The score $$s$$ of the hitchhiker that will finally be chosen if the above procedure is followed.

Example

Input:

19
0.2583
0.1580
0.4293
0.2299
0.2443
0.1043
0.0632
0.0363
0.1381
0.9899
0.3766
0.7932
0.7567
0.1048
0.9148
0.3787
0.7712
0.1390
0.4001

Output:

0.9899