Interactive
Alex_KPR: — ...начиная где-то с декартовых деревьев, FFT и так далее, вбивание и отладка кода становятся напрягающими и довольно занудными задачами...
Kunyavsky: — А можно я придерусь к мелочи. Что делают в одном ряду по времени написания декартово дерево и FFT?
Alex_KPR: — это первое, что пришло в голову, где нужно много писать и есть где накосячить
Kunyavsky: — Я же сказал: придираюсь к мелочам. Просто на мой взгляд рядом поставлены вещи, одна из которых несравнимо легче по написанию
homo_sapiens: — Полностью согласен Фурье пишется вдвое может даже втрое быстрее чем дерево (но его обычно пихать надо руками и ногами)
Kunyavsky: — Я имел ввиду с точностью наоборот. Все таки очень специфичная тема.
homo_sapiens: — Видимо и правда на вкус и цвет...
Прийшов час дізнатись, що ж простіше.
Вам пропонується дві послідовності з N цілих чисел {x_i} та {y_i}.
Якщо вам більше подобається FFT, уявіть, що це коефіцієнти двох многочленів:
Знайдіть коефіцієнти многочлена P(z)·Q(z).
Якщо ж вам більше подобаються Декартові дерева, уявіть, що {x_i} — ключі, а {y_i} — приорітети. Побудуйте Декартове дерево шляхом вставки у нього послідовно усіх N елементів (x_i, y_i). Після кожної вставки виводьте висоту отриманого дерева. Висота дерева — кількість ребер на найдовшому шляху від довільної вершини до кореня.
Для тих, хто обрав FFT, нагадаємо, що Декартове дерево — це двійкове дерево пошуку за ключами, які містяться у вершинах (x_i). І одночасно куча за приорітетами в вершинах (y_i). Тобто, для кожної вершини дерева виконується властивість, що усі вершини з лівого піддерева мають ключі менші, ніж у даній вершині, а усі вершини з правого піддерева — більші. А також приорітет даної вершини більше приорітета її синів.
Незалежно від того, що ж ви вибрали, автор переконливо просить не викорстовувати у цій задачі prewritten code.
Вхідні дані
У першому рядку число N. У другому рядку N різних цілих чисел — {x_i}. У треому рядку N різних цілих чисел — послідовність {y_i}.
Вихідні дані
Якщо ви вибрали FFT, то виведіть 2N-1 цілих чисел — коефіцієнти результуючого многочлена. Якщо Декартове дерево, то N цілих чисел — висоти дерева після вставки у нього кожної вершини.
Взагалі, ви можете вивести і те, і те, але тоді обидва результати будуть перевірятись на коректність.
Обмеження
1 ≤ N ≤ 50000
1 ≤ x_i ≤ 50000
1 ≤ y_i ≤ 50000
Гарантується, що висота дерева не перевищить 50.