分数: 300 点
问题陈述
有 N 麻糬(年糕)按大小升序排列。 尺寸 i-第麻糬 (1 \leq i \leq N) is A_i.
给了两个麻糬 A 和 B,有尺寸 a 和 b 分别,您可以通过放置麻糬来制作一个镜饼(一种堆叠的年糕) A 在麻糬上面 B 当且仅当 a 最多为一半 b.
您从其中选择两个麻糬 N 年糕,然后将一个放在另一个上面,形成一个镜饼。
找出可以制作多少种不同的镜饼。
如果至少一个年糕不同,则即使年糕的大小相同,也可以区分两个镜饼。
约束
- 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 \cdots A_N
输出
打印可以制作的不同种类镜饼的数量。
示例输入 1
6 2 3 4 4 7 10
示例输出 1
8
给定麻糬的尺寸如下:

这种情况下,您可以制作以下八种镜饼:

请注意,镜饼有两种,其中麻糬的大小 4 上面有一个大小的麻糬 2,以及两种尺寸的麻糬 10 上面有一个大小的麻糬 4.
示例输入 2
3 387 388 389
示例输出 2
0
您可能无法制作镜饼。
示例输入 3
32 1 2 4 5 8 10 12 16 19 25 33 40 50 64 87 101 149 175 202 211 278 314 355 405 412 420 442 481 512 582 600 641
示例输出 3
388