解题思路

• 核心目标：通过若干次“把某个数 ai 拆成两个正整数相加”的操作，使数组满足 max(a) ≤ 2 × min(a)。

• 关键观察：

  • 拆分会让元素变小，但不能让当前最小值变小，否则条件更难满足。因此最优策略是不拆分最小值，并在拆分其他元素时尽量让拆出的每一段都 ≥ 最小值 m。
  • 若数组最小值为 m，只要把每个元素 ai 拆成若干段，使每段都 ≤ 2m 且 ≥ m，就能保证最终整体满足条件，同时不降低 m。

• 化为计数问题：

题目内容

在游戏中，主人公 $Tk$有一个长度为{$a_1,a_2,...,a_n$}的数组 ； 他将一个数组称为令人心动，当且仅当该数组的最大值不超过最小值的两倍，即$max(a_1,...,a_n)≤2×min(a_1,...,a_n)$； 为了让自己的数组变为令人心动，他可以进行以下操作多次，直到满足条件：

• 选择一个元素$a_i$，并选取两个正整数 $x,y$满足$x+y=a_i$ ，将$a_i$删除，并将$x,y$插入数组中； 请你计算使数组变为令人心动所需的最少操作次数。

输入描述

第一行输入一个整数$n(1≤n≤2×10^5)$，表示数组的长度； 第二行输入$n$个整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$，表示数组中的元素。

输出描述

输出一个整数，表示将数组变为令人心动的最少操作次数。

样例1

输入

3
3 6 13

输出

2

说明

• 说明 在此样例中，初始数组为 {$3,6,13$}，操作方案不唯一；
• 将 $13$ 拆分为$5$ 和$8$，数组变为{$3,6,5,8$} ；
• 将 $8$ 拆分为 $4$和$4$，数组变为{$3,6,5,4,4$} ，此时最大值 $6$ 不超过最小值 $3$ 的两倍，满足条件，共需 $2$次操作。