盆栽布景

1s, 512MB

题目描述

园艺店计划打造一组创意盆栽布景，新进了 $n$ 盆品种相同的盆栽，每盆盆栽的株冠直径（枝叶自然展开后的最大直径）为 $c_i$。所有盆栽已按照株冠直径非递减的顺序排列好。

为实现紧凑美观的陈列效果，你将按照如下规则布景：若两盆盆栽 $x,y$ 的株冠直径 $c_x, c_y$ 满足 $c_x\le \frac{c_y}{2}$，则可以将盆栽 $x$ 移入盆栽 $y$ 的花盆内，形成 “组合盆景”；特别地，一盆盆栽 $x$ 最多只能移入另外一盆盆栽 $y$ 中，不可以同时移入多盆盆栽。

请问这 $n$ 盆盆栽最多能形成多少组“组合盆景”？

输入格式

第一行一个整数 $n$，代表盆栽数

第二行 $n$ 个整数 $c[1\sim n]$ 代表每盆盆栽的株冠直径

输出格式

一行一个整数代表答案

输入输出样例 #1

输入 #1

5
2 3 4 7 10

输出 #1

2

输入输出样例 #2

输入 #2

3
387 388 389

输出 #2

0

样例解释

对于样例 $1$，满足条件的“组合盆景”有：$c_1=2$ 与 $c_5=10$、$c_2=3$ 与 $c_4=7$

数据范围

对于 $40\%$ 的数据，$2\le n\le 10^3, 1\le c_i\le 10^5$

对于 $100\%$ 的数据，$2\le n\le 5\times 10^5, 1\le c_i\le 10^6$，保证 $c_1\sim c_n$ 非递减