题目描述

你最喜欢的音乐平台汪汪音乐为你专门制作了一个音乐播放列表。该播放列表由编号从 $1$ 到 $n$ 的 $n$ 首歌曲组成。播放列表是自动循环的：当播放完第 $i$ 首歌曲后，会自动开始播放第 $i+1$ 首歌曲；播放完第 $n$ 首歌曲后，又会自动开始播放第 $1$ 首歌曲。

对于每首歌曲 $i$，你估计了它的酷度为 $a_i$。酷度 $a_i$ 越高，歌曲 $i$ 就越酷。

每天早上，你会选择一首歌曲。然后播放列表会按照通常的循环方式从这首歌曲开始播放。在任何时刻，你都会记住已经播放歌曲的最大酷度 $x$。一旦你听到酷度严格小于 $\frac{x}{2}$（不进行四舍五入）的歌曲开始播放，你会立即关闭音乐以保持好心情。

对于每首歌曲 $i$，找出从你早上选择第 $i$ 首歌曲开始听歌到关闭音乐之前你会听多少首歌曲，或者确定你将无限期地听音乐。请注意，如果你多次听同一首歌曲，每次都必须计数。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 10^5$），表示播放列表中的歌曲数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每首歌曲的酷度。

输出格式

输出 $n$ 个整数 $c_1, c_2, \ldots, c_n$，其中 $c_i$ 要么是你从第 $i$ 首歌曲开始听会听多少首歌曲，要么是 $-1$ 如果你将无限期地听音乐。

样例

4
11 5 2 7

1 1 3 2

4
3 2 5 3

5 4 3 6

3
4 3 6

-1 -1 -1

说明/提示

样例解释

在第一个示例中，如果你从...开始，会发生以下情况

• 第 $1$ 首歌曲：听第 $1$ 首歌曲，当 $a_2 \lt \frac{a_1}{2}$ 时停止。
• 第 $2$ 首歌曲：听第 $2$ 首歌曲，当 $a_3 \lt \frac{a_2}{2}$ 时停止。
• 第 $3$ 首歌曲：听第 $3$ 首歌曲，听第 $4$ 首歌曲，听第 $1$ 首歌曲，当 $a_2 \lt \frac{\max(a_3, a_4, a_1)}{2}$ 时停止。
• 第 $4$ 首歌曲：听第 $4$ 首歌曲，听第 $1$ 首歌曲，当$a_2 \lt \frac{\max(a_4, a_1)}{2}$时停止。

在第二个示例中，如果你从第 $4$ 首歌曲开始，你会听第 $4$ 首歌曲，听第 $1$ 首歌曲，听第 $2$ 首歌曲，听第 $3$ 首歌曲，再次听第 $4$ 首歌曲，再次听第 $1$ 首歌曲，当 $a_2 \lt \frac{max(a_4, a_1, a_2, a_3, a_4, a_1)}{2}$ 时停止。请注意，第 $1$ 首歌曲和第 $4$ 首歌曲都被计入结果两次。

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 100, a_i \le 1000$
• 对于 $100\%$ 的数据，$2 \le n \le 10^5, 1 \le a_i \le 10^9$