← 返回题目列表

Codeforces · 1029/B

B. 创建比赛

中文机器翻译题面 查看原题

给你一个由 $$$n$$$ 问题组成的问题集。第 $$$i$$$ 问题的难度为 $$$a_i$$$。保证所有困难都是不同的,并且按递增顺序给出。

您必须组织由给定问题集中的一些问题组成的竞赛。换句话说,您必须组织的竞赛应该是给定问题集的问题子集(不一定是连续的)。只需要满足一个条件:对于每个问题,但最难的问题(难度最大的问题)应该有一个问题的难度大于该问题的难度,但不大于该问题难度的两倍。换句话说,令 $$$a_{i_1}, a_{i_2}, \dots, a_{i_p}$$$ 为所选问题按升序排列的难度。那么对于从 $$$1$$$ 到 $$$p-1$$$ $$$a_{i_{j + 1}} \le a_{i_j} \cdot 2$$$ 的每个 $$$j$$$ 应该成立。这意味着仅包含一个问题的竞赛始终有效。

在满足上述条件的所有竞赛中,您必须组装一个问题数量最多的竞赛。你的任务是找到这么多问题。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 问题集中的问题数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 问题的难度。保证问题的难点是明显的,并按递增的顺序给出。

输出

打印一个整数 - 竞赛中满足问题陈述中的条件的最大问题数。

示例

输入 #1

10
1 2 5 6 7 10 21 23 24 49

输出 #1

4

输入 #2

5
2 10 50 110 250

输出 #2

1

输入 #3

6
4 7 12 100 150 199

输出 #3

3

注意

第一个示例的描述:有 $$$10$$$ 有效竞赛由 $$$1$$$ 问题组成,$$$10$$$ 有效竞赛由 $$$2$$$ 问题组成 ($$$[1, 2], [5, 6], [5, 7], [5, 10], [6, 7], [6, 10], [7, 10]、[21, 23]、[21, 24]、[23, 24]$$$)、$$$5$$$ 包含 $$$3$$$ 问题的有效竞赛 ($$$[5, 6, 7], [5, 6, 10], [5, 7, 10], [6, 7, 10], [21, 23, 24]$$$)和一个由 $$$4$$$ 问题组成的有效竞赛($$$[5, 6, 7, 10]$$$)。

在第二个示例中,所有有效竞赛均包含 $$$1$$$ 问题。

在第三个示例中,有两个由 $$$3$$$ 问题组成的竞赛:$$$[4, 7, 12]$$$ 和 $$$[100, 150, 199]$$$。