/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
N 個の餅が小さいほうから順に並んでいます。 i 番目 (1\leq i\leq N) の餅の大きさは A _ i です。
2 つの餅 A,B の大きさをそれぞれ a,b としたとき、a が b の半分以下であるとき、かつそのときに限り、餅 A を餅 B の上に乗せて鏡餅を 1 つ作ることができます。
同時にいくつの鏡餅を作ることができるか求めてください。
より厳密には、以下ができるような最大の非負整数 K を求めてください。
- N 個の餅から 2K 個の餅を選んで K 個の 2 つ組に分け、それぞれの組について一方をもう一方の上に乗せることで鏡餅を 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\lt N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \dotsc A _ N
出力
同時に K 個鏡餅を作れるような最大の K を出力せよ。
入力例 1
6 2 3 4 4 7 10
出力例 1
3
与えられた餅の大きさは以下のようになっています。
このとき、以下の 3 つの鏡餅を同時に作ることができます。
6 つの餅から 4 つ以上の鏡餅を作ることはできないので、3 を出力してください。
入力例 2
3 387 388 389
出力例 2
0
鏡餅を 1 つも作ることができない場合もあります。
入力例 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
Score : 450 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.
Find how many kagamimochi can be made simultaneously.
More precisely, find the maximum non-negative integer K for which the following is possible:
- From the N mochi, choose 2K of them to form K pairs. For each pair, place one mochi on top of the other, to make K kagamimochi.
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 \dotsc A_N
Output
Print the maximum K such that K kagamimochi can be made simultaneously.
Sample Input 1
6 2 3 4 4 7 10
Sample Output 1
3
The sizes of the given mochi are as follows:
In this case, you can make the following three kagamimochi simultaneously:
It is not possible to make four or more kagamimochi from six mochi, so print 3.
Sample Input 2
3 387 388 389
Sample Output 2
0
It is possible that you cannot make any kagamimochi.
Sample Input 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
Sample Output 3
6