Склейка журналов двух роботов

В мастерской два робота ведут журналы событий. Каждый робот записывает номера «тиков» (целые числа), когда у него что-то произошло. Внутри одного журнала записи уже идут по неубыванию.

Диспетчеру нужен единый журнал: все тики из обоих журналов, тоже по неубыванию. Если одинаковый тик встречается у обоих роботов или несколько раз у одного — в итоговом журнале он должен встретиться столько же раз.

Формат ввода

В первой строке дано целое число m — количество записей в журнале первого робота. Во второй строке дано m целых чисел a1..am в неубывающем порядке. В третьей строке дано целое число n — количество записей в журнале второго робота. В четвёртой строке дано n целых чисел b1..bn в неубывающем порядке.

Формат вывода

Выведите m+n целых чисел — объединённый журнал в неубывающем порядке.

Ограничения

• 1 ≤ m ≤ 8000
• 2 ≤ n ≤ 8000
• -10^9 ≤ ai, bi ≤ 10^9
• оба массива отсортированы по неубыванию

Пример

Ввод:

4
-2 0 3 3
3
-5 3 10

Вывод:

-5 -2 0 3 3 3 10

Ключевое наблюдение: оба журнала уже отсортированы. Значит, чтобы получить общий отсортированный список, не нужно ничего «пересортировывать» — достаточно аккуратно сливать их, как в merge sort.

Приём: два указателя. Держим позиции i в первом массиве и j во втором. В каждый момент минимальный из ещё не взятых тиков — это либо a[i], либо b[j]. Берём меньший и двигаем соответствующий указатель. Если значения равны — можно брать любой (например, из a), а второй такой же тик попадёт позже, когда сравнение дойдёт до него. Так автоматически сохраняются все повторы.

План:

• Считать m, массив a, затем n, массив b.
• Поставить i = 0, j = 0, завести список out.
• Пока i < m и j < n:
• если a[i] <= b[j], добавить a[i] и сделать i += 1, иначе добавить b[j] и сделать j += 1.
• Когда один массив закончился, дописать в ответ «хвост» второго (в нём всё уже не меньше предыдущего).
• Вывести out.

Мини-сниппет сравнения: if a[i] <= b[j]: take a[i], i += 1 else: take b[j], j += 1

Сложность: O(m + n) по времени, потому что каждый указатель двигается только вперёд, и O(m + n) по памяти для ответа.

Частая ошибка: при a[i] == b[j] делать i += 1 и j += 1 одновременно — так вы потеряете один из повторов. Нужно добавлять элементы по одному.