在你的面前从左到右摆放着 $n$ 根长短不一的木棍，你每次可以折断一根木棍，并将折断后得到的两根木棍一左一右放在原来的位置（即若原木棍有左邻居，则两根新木棍必须放在左邻居的右边，若原木棍有右邻居，新木棍必须放在右邻居的左边，所有木棍保持左右排列）。折断后的两根木棍的长度必须为整数，且它们之和等于折断前的木棍长度。你希望最终从左到右的木棍长度单调不减，那么你需要折断多少次呢？

输入描述

第一行是一个数 $n$，表示开始时有多少根木棍 $(1<=n<=3000)$ 第二行有 $n$ 个数，从第 $1$ 个到第 $n$ 个分别表示从左到右的木棍长度。对任意木棍的长度 $l$，有 $1<=l<=3000$。

输出描述

输出一行，一个数，你最少所需的折断木棍的次数 $x$

示例

输入:
5
3 5 13 9 12

输出:
1

说明
你可以将长度为 $13$ 的木棍折成长度分别为 $5$ 和 $8$ 的两根木棍，最终得到的排列是 3 5 5 8 9 12