Разбор

Интервал $A[i...j]$ будем называть хорошим, если на нем находятся числа в промежутке $[A_i;2\cdot A_i]$ включительно (то есть $A_j\le 2\cdot A_i$).

Реализуем скользящее окно при помощи двух указателей $i$ и $j$ и будем его поддерживать так, чтобы текущий рассматриваемый интервал $[i...j]$ был хорошим, а интервал $[i...j+1]$ плохим.

Например, для следующей последовательности

• интервалы $[2;2],[2;3],[2;4]$ и $[2;5]$ являются хорошими.

• интервалы $[2;6],[2;7]$ являются плохими.

Если $A_j\le 2\cdot A_i$, то расширяем текущий интервал до $А[i...j+1]$. Иначе сокращаем его до $А[i+\mathrm{1...}j]$. Перед передвижением указателя $i$ выводим количество элементов, лежащих между $A_i$ и $2\cdot A_i$ включительно. Оно равно $j-i$.

Оценка сложности алгоритма линейная, то есть $O(n)$.

Пример

Рассмотрим движение указателей для приведенного примера.

Для заданного состояния $A_j\le 2\cdot A_i$, поэтому двигаем вперед указатель $j$.

Теперь $A_j>2\cdot A_i$. Вперед следует двигать указатель $i$. Однако перед его перемещением выводим количество элементов, лежащих между $A_i$ и $2\cdot A_i$ включительно. Оно равно $j-i=6-2=4$.

Двигаем $j$ вперед пока $A_j\le 2\cdot A_i$.

Теперь $A_j>2\cdot A_i$. Выводим ответ для $i=3$ (он равен $j-i=8-3=5$) и увеличиваем $i$ на $1$.

Реализация алгоритма

Читаем входные данные.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &a[i]);

Инициализируем указатели $i=j=0$.

i = j = 0;

Двигаем указатели вперед пока для каждого значения $i<n$ не будет найден ответ.

while (i < n) // [i..j]
{

Если $A_j\le 2\cdot A_i$ (но при этом $j$ не вышло за границы массива, то есть $j<n$), то расширяем текущий интервал, увеличивая указатель $j$.

  if ((j < n) && (a[j] <= 2 * a[i])) j++;
  else
  {

При $A_j>2\cdot A_i$ выводим ответ для индекса $i$ и увеличиваем $i$ на единицу.

    printf("%d ", j - i);
    i++;
  }
}

Реализация алгоритма — бинарный поиск, O(n log n)

Читаем входные данные.

scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
  scanf("%d", &v[i]);

Для каждого индекса $i<n$ при помощи бинарного поиска ищем такое наибольшее значение индекса $x$, что на интервале $[i;x-1]$ находятся числа от $A_i$ до $2\cdot A_i$, а $A_x>2\cdot A_i$. Количество чисел на интервале $[i;x-1]$ равно $x-i$.

for (i = 0; i < n; i++)
{
  x = upper_bound(v.begin(), v.end(), 2 * v[i]) - v.begin();
  printf("%d ", x - i);
}

Java реализация

import java.util.*;
 
public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int m[] = new int[n];
    for(int i = 0; i < n; i++)
      m[i] = con.nextInt();

    int i = 0, j = 0;
    while (i < n) // [i..j]
    {
      if ((j < n) && (m[j] <= 2 * m[i])) j++;
      else
      {
        System.out.print(j - i + " ");
        i++;
      }
    }

    con.close();
  }
}

Python реализация

Читаем входные данные.

n = int(input())
lst = list(map(int,input().split()))

Инициализируем указатели $i=j=0$.

i = j = 0

Двигаем указатели вперед пока для каждого значения $i<n$ не будет найден ответ.

while (i < n): # [i..j]

Если $A_j\le 2\cdot A_i$ (но при этом $j$ не вышло за границы массива, то есть $j<n$), то расширяем текущий интервал, увеличивая указатель $j$.

  if (j < n and lst[j] <= 2 * lst[i]):
    j += 1
  else:

При $A_j>2\cdot A_i$ выводим ответ для индекса $i$ и увеличиваем $i$ на единицу.

    print(j - i, end=" ");
    i += 1

Python реализация — бинарный поиск, O(n log n)

from bisect import bisect_right

Читаем входные данные.

n = int(input())
v = list(map(int, input().split()))

Для каждого индекса $i<n$ при помощи бинарного поиска ищем такое наибольшее значение индекса $x$, что на интервале $[i;x-1]$ находятся числа от ${А}_i$ до $2\cdot A_i$, а $A_x>2\cdot A_i$. Количество чисел на интервале $[i;x-1]$ равно $x-i$.

for i in range(n):
  x = bisect_right(v, 2 * v[i])
  print(x - i, end=" ")