#ABC388C. 各种各样的镜饼

各种各样的镜饼

AT_abc388_c [ABC388C] Various Kagamimochi

题目描述

\hspace{15pt}有 nn 个饼。第 ii 个饼的大小为 ai(1≦i≦n)a_i \left(1 \leqq i \leqq n\right)。

\hspace{15pt}对于两个大小分别为 xx 和 yy 的饼,如果 xx 小于或等于 yy 的一半,即 x≦y2x \leqq \frac{y}{2},则可以将大小为 xx 的饼放在大小为 yy 的饼上,制作一个“镜饼”。

\hspace{15pt}从 nn 个饼中任选两个,使得其中一个饼放在另一个饼上制作一个“镜饼”。需要求出可以制作多少种不同的“镜饼”。

\hspace{15pt}此外,即使构成镜饼的饼的大小相同,只要至少有一个是不同的饼,就可以算作是另一种类型的镜饼。

输入格式

\hspace{15pt}第一行输入一个整数 n(2≦n≦5×105)n \left(2 \leqq n \leqq 5 \times 10^5\right) 代表饼的数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^9\right)$ 代表每个饼的大小。保证 ai≦ai+1(1≦i<n)a_i \leqq a_{i+1} \left(1 \leqq i < n\right)。

输出格式

\hspace{15pt}在一行上输出一个整数,代表可以制作的镜饼种数。

测试样例

6
2 3 4 4 7 10
8
3
387 388 389
0
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
388