该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

显然，如果直接跑步的话太慢了，因此，小A需要利用虫洞进行快速旅行。

题目描述

现在有 $n$ 个虫洞，第 $i$ 个虫洞的能量值为 $a_i$。小A希望能在虫洞中进行连续跳跃。

我们称这 $n$ 个虫洞能进行连续跳跃，当且仅当这 $n$ 个虫洞的能量值是 有序 的 （从大到小或从小到大都行）。

显然目前的虫洞不太可能满足进行连续跳跃的条件，因此，小A需要使用虫洞修改器，将一个虫洞分解成两个虫洞，这两个新的虫洞的能量值之和等于原来的虫洞。

由于虫洞修改器会引起能量波动，G国很可能定位这里，所以小A希望尽可能少用虫洞修改器。

他现在想知道最少需要使用多少次虫洞修改器，才能使虫洞能够进行连续跳跃。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

输出答案。

样例 #1

样例输入 #1

3
3 5 2

样例输出 #1

4

提示

对于 $10\%$ 的数据，$n \le 10$。

对于 $50\%$ 的数据，$n,a_i \le 100$。

对于 $70\%$ 的数据，$n \le 10^5$，$a_i \le 10^9$。

对于 $100\%$ 的数据，$n \le 10^6$，$a_i \le 10^9$。