You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

有 2N 张牌，它们的点数分别为 1 到 2N 。Bessie 拿了其中的 N 张，Elsie 拿了剩下的 N 张。

Bessie 和 Elsie 会进行 N 轮游戏，在每轮游戏中，Bessie 和 Elsie 各出一张牌。出了的牌不能收回。

Bessie可以选择一个0~~N中的整数K。

在前 K 轮中，谁的牌点数大谁就得一分；在后 N-K 轮中，谁的牌点数小谁就得一分。

已知 Elsie 每一轮会出什么牌，试求 Bessie 最多能得多少分。 2≤N≤50000, 保证 N 是偶数。

Format

Input

第一行一个N。 接下来N行，每行一个数。第i+1行的数表示第 i 轮Elsie会出的牌的点数。

Output

Bessie的最大得分。

Samples

输入1

4
1
8
4
3

输出1

3

Limitation

33% 的数据， $N \le 100$

$2 \le N \le 50000$