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.

Description

$Mirko$ 在阁楼里发现了 $N$ 个链。每个链由一些环组成，其中每个环最多有两个相邻环。每个环都可以打开或合上，因此可以将链分开或连成更长的链。

$Mirko$ 希望把所有链连成一条巨大的链，并且打开或合上尽可能少的环。

例如，假设 $Mirko$ 只有 $3$ 个链，每个链只有一个环，他可以打开其中一个，并且连上另外两个再合上，例如下图的过程：

给定链的数量以及每个链的长度，找到 $Mirko$ 必须打开和关闭的最小环数，使它们全部在一个长链上。

Input Format

第一行一个整数 $N\ (2\le N\le 5\times 10^5)$，表示链的数量。

第二行 $N$ 个正整数 $L_i\ (1\le L_i\le 10^6)$，表示第 $i$ 个链的长度。

Output Format

输出仅一行一个整数，表示最少要打开的节数。

2
3 3

1

3
1 1 1

1

5
4 3 5 7 9

3