题目描述

一个有强迫症的科学家特别喜欢捉弄可怜的细胞。

细胞现在正排成一排，瑟瑟发抖。但科学家还是很不满意，因为细胞有大有小，没有按照科学家的心愿进行有序的排列。于是科学家决定自己动手，一刀两断！！！

科学家每次出刀都能将一个细胞劈成两半，这两半的大小相加等于原细胞。在不停地劈砍下，细胞终于变成有序的排列了！

求将所有细胞劈成非递减序列的最小劈砍的次数。

输入格式 第一行有一个整数 n，输入有多少个细胞排列在一行上。

第二行输入一个数组 cell，数组长度为 n，数字用空格分隔，代表每个细胞的大小。

输出格式 输出一行，共一个数，表示最少用多少刀能将所有细胞劈成非递减序列。

样例

Input 1

3

3 9 3

Output 1

2

Input 2

3

3 5 2

Output 2

4

Input 3

7

3 4 7 6 11 17 14

Output 3

7

Input 4

10

7 5 4 6 11 17 15 23 46 9

Output 4

25

样例解释

科学家第一刀将大小为9的细胞劈成3和6。现在细胞的排列是[3,3,6,3] 科学家第二刀将大小为6的细胞劈成3和3。现在细胞的排列是[3,3,3,3,3]，是有序的序列

科学家用了两刀将大小为5的细胞劈成[1,2,2] 科学家用了两刀将大小为3的细胞劈成[1,1,1] 现在细胞的排列是[1,1,1,1,2,2,2]，为非递减序列

数据范围

对于20%的数据来说

1 <= n <= 100

1 <= cell[i] <= 100

对于100%的数据来说

1 <= n <= 1e5

1 <= cell[i] <= 1e9