Question

C++!! Upper bound

На вход подаются N целых чисел, а также набор из M запросов, каждый из которых — целое число. Ваша задача — для каждого запроса найти количество чисел из исходного набора, меньших либо равных заданному в запросе числу. Использовать встроенные функции бинарного поиска запрещено.


Входные данные


Первая строка содержит число N — количество элементов в массиве. 1≤N≤250000.

Вторая строка содержит N целых чисел Ai через пробел. −10^9≤Ai≤10^9.

Третья строка содержит число M — количество запросов. 1≤M≤250000.

Четвёртая строка содержит M целых чисел Qi через пробел. −10^9≤Qi≤10^9.


Выходные данные


Выведите единственную строку с M целыми числами — количествами чисел исходного массива, меньших либо равных соответствующему запросу.


Примеры

Ввод

5

1 5 3 2 1

2

4 3

Вывод

4 4

Ограничения

Время выполнения: 3 секунды

Answer 1

#include <iostream>

using namespace std;

int main() {

int N;

cin >> N;

long* arrN = new long[N];

for (int i = 0; i < N; ++i) {

 cin >> arrN[i];

}

int M;

cin >> M;

long* arrM = new long[M];

for (int i = 0; i < M; ++i) {

 cin >> arrM[i];

}

for (int i = 0; i < M; ++i) {

 int count = 0;

 for (int j = 0; j < N; ++j) {

  if (arrN[j] <= arrM[i]) {

   ++count;

  }

 }

 cout << count << " ";

}

}