Mirko 在阁楼里找到了 $N$ 条链子。每条链子由若干个链环组成，其中每个链环最多与两个相邻的链环相连。每个链环都可以被打开或关闭，因此可以将链子拆开或连接成更长的链子。Mirko 希望将所有链子连接成一条巨大的链子，同时尽可能少地打开和关闭链环。

例如，如果 Mirko 只有三条链子，每条链子都只由一个链环组成，他可以打开其中一个链环，用它连接剩下的两条链子，然后将其关闭：

给定链子的数量和每条链子的长度，求 Mirko 为了将它们全部连接成一条长链而必须打开和关闭的链环的最小数量。

输入格式

输入的第一行包含一个正整数 $N$ ($2 \le N \le 500\,000$)，表示链子的数量。

输入的第二行包含 $N$ 个正整数 $L_i$ ($1 \le L_i \le 1\,000\,000$)，表示每条链子的长度。

输出格式

输出的第一行也是唯一的一行，应包含所需的最小链环数量。

样例

输入样例 1

2
3 3

输出样例 1

1

输入样例 2

3
1 1 1

输出样例 2

1

输入样例 3

5
4 3 5 7 9

输出样例 3

3

说明

样例 1 说明：Mirko 可以打开第一条链子的最后一个链环，将其与第二条链子的第一个链环相连，然后关闭它。

样例 3 说明：这里最好是将长度为 $3$ 的链子完全拆开，用它的三个链环来连接剩下的链子。