/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。
2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。
N 個の餅から 2 つの餅を選び、一方をもう一方の上に乗せることで鏡餅を 1 つ作ります。
何種類の鏡餅を作ることができるか求めてください。
ただし、鏡餅を構成する餅の大きさが同じでも、少なくとも一方が異なる餅であれば別の種類の鏡餅として数えます。
制約
- 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\lt N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \cdots A _ N
出力
作ることができる鏡餅の種類数を出力せよ。
入力例 1
6 2 3 4 4 7 10
出力例 1
8
与えられた餅の大きさは以下のようになっています。
このとき、以下の 8 種類の鏡餅を作ることができます。
大きさ 4 の餅の上に大きさ 2 の餅を乗せた鏡餅や、大きさ 10 の餅の上に大きさ 4 の餅を乗せた鏡餅は 2 種類あることに注意してください。
入力例 2
3 387 388 389
出力例 2
0
鏡餅を 1 種類も作ることができない場合もあります。
入力例 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
Score : 300 points
Problem Statement
There are N mochi (rice cakes) arranged in ascending order of size. The size of the i-th mochi (1 \leq i \leq N) is A_i.
Given two mochi A and B, with sizes a and b respectively, you can make one kagamimochi (a stacked rice cake) by placing mochi A on top of mochi B if and only if a is at most half of b.
You choose two mochi out of the N mochi, and place one on top of the other to form one kagamimochi.
Find how many different kinds of kagamimochi can be made.
Two kagamimochi are distinguished if at least one of the mochi is different, even if the sizes of the mochi are the same.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the number of different kinds of kagamimochi that can be made.
Sample Input 1
6 2 3 4 4 7 10
Sample Output 1
8
The sizes of the given mochi are as follows:
In this case, you can make the following eight kinds of kagamimochi:
Note that there are two kinds of kagamimochi where a mochi of size 4 is topped by a mochi of size 2, and two kinds where a mochi of size 10 is topped by a mochi of size 4.
Sample Input 2
3 387 388 389
Sample Output 2
0
It is possible that you cannot make any kagamimochi.
Sample Input 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
Sample Output 3
388