← 返回题目列表

AtCoder · abc388_e

H. 同时镜饼

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

分数: 450 点

问题陈述

有 N 麻糬(年糕),按大小升序排列。 尺寸 i-第麻糬 (1\leq i\leq N) is A_i.

给了两个麻糬 A 和 B,有尺寸 a 和 b 分别,您可以通过放置麻糬来制作一个镜饼(一种堆叠的年糕) A 在麻糬上面 B 当且仅当 a 最多为一半 b.

找出可以同时制作多少镜饼。

更准确地说,找到最大非负整数 K 可以执行以下操作:

  • 从 N 麻糬,选择 2K 其中形成 K 对。对于每一对,将一个麻糬放在另一个上面,以制作 K 镜饼。

约束

  • 2 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)
  • A_i \leq A_{i+1} \ (1 \leq i < N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dotsc A_N

输出

打印最大 K 这样 K 镜饼可以同时制作。


示例输入 1

6
2 3 4 4 7 10

示例输出 1

3

给定麻糬的尺寸如下:

在这种情况下,您可以同时制作以下三个镜饼:

不可能用六个麻糬制作四个或更多镜饼,所以打印 3.


示例输入 2

3
387 388 389

示例输出 2

0

您可能无法制作镜饼。


示例输入 3

24
307 321 330 339 349 392 422 430 477 481 488 537 541 571 575 602 614 660 669 678 712 723 785 792

示例输出 3

6