题目描述

小A所在的单位举办扑克比赛。 比赛的规则非常独特。共有牌面值为 1~2N 的 2N 张牌，所有牌面值互不相同。参赛的两位选手小A和小B各持有其中的 N 张。比赛分为 N 轮，双方按顺序各出一张牌进行比拼。 比赛分为两个阶段： 前一半轮次（前 N/2 轮）：牌面值较大的一方得 1 分。 后一半轮次（后 N/2 轮）：牌面值较小的一方得 1 分。 如果小A可以预知小B的全部出牌顺序，并根据小B的出牌顺序安排自己的出牌，以获得尽可能多的得分。 请问小A最多能得到多少分？

输入格式

第一行输入一个整数 N，N 一定是偶数。 接下来 N 行，每行一个整数，表示小B在每一轮中将会打出的卡牌面值，也就是小B的出牌顺序。 可以由此推导出小A手中的所有卡牌的面值。

输出格式

输出一个整数，表示小A能获得的最大得分。

样例输入 1

4
8
2
6
1

样例输出 1

2

样例输入 2

6
12
10
6
2
4
1

样例输出 2

3

样例输入 3

10
20
19
18
1
12
9
8
16
11
13

样例输出 3

7

样例说明

所有卡牌面值为 1~8。 小B持有的卡牌为 {8, 2, 6, 1}，因此小A持有 {7, 5, 4, 3}。 在前两轮（面值较大取胜阶段），小A可用 5,7 对战小B的 8,2，可以得到 1 分（7 > 2）。 在后两轮（面值较小取胜阶段），小A可用 4,3 对战小B的 6,1，可以得到 1 分（4 < 6）。 总得分为 2 分。

数据范围

• 对于 100% 的测试数据，满足 2 ≤ N ≤ 50000，所有卡牌面值均为 1~2*N 的互不相同整数。
• 测试点 1~2：N ≤ 20，具备特殊性质 A 和 B。
• 测试点 3~5：N ≤ 100，具备特殊性质 A。
• 测试点 6~15：N ≤ 50000，无特殊性质。

特殊性质说明

• 特殊性质 A：保证读入的 N 个数已按照降序排序（样例数据 2 满足该性质）。
• 特殊性质 B：保证读入的 N 个数都是奇数。