Tourism Product

Interview

Time limit1sMemory limit1024 MB

Summary

Given N beauty values, find the largest median over all contiguous segments of at least two attractions.

Level: Medium5 of 10
Topics: Binary search, Prefix sum
Solved: No attempts yet

Problem

Mingyeom is planning a new tourism product. The product is a course that visits several attractions. There are $N$ attractions numbered from 1 to $N$ , and each attraction has a beauty that can be expressed as a positive integer. When Mingyeom adds attractions to the product, he can only add attractions with consecutive numbers. For example, he can add attractions 3, 4, and 5, but he cannot add attractions 2, 4, and 5 while leaving out attraction 3. The product must include at least two attractions.

A tourist gets satisfaction equal to the median beauty of the attractions in the product. The median of $K$ numbers is the $\lfloor \frac{K+1}{2}\rfloor$ -th number after the numbers are sorted in non-decreasing order, meaning each number is greater than or equal to the one before it.

Based on this, Mingyeom developed a product that maximizes the tourist satisfaction. Find the satisfaction of the product Mingyeom developed.

Input

The first line contains the number of attractions $N$ . ( $2 \le N \le 200\,000$ )

The second line contains $N$ integers between $1$ and $10^9$ , separated by spaces. The $i$ -th integer is the beauty of attraction $i$ .

Output

Print the satisfaction of the product Mingyeom developed on the first line.

Examples2

Example 1
Input
```
5
4 9 7 6 9
```
Expected output
```
7
```
Example 2
Input
```
5
2 1 2 1 1
```
Expected output
```
2
```