\href{http://codeforces.ru/blog/entry/4037}{http://codeforces.ru/blog/entry/4037} \includegraphics{https://static.e-olymp.com/content/5a/5a455f8d436fd6f1fa92bfb353bad4978d280e9f.jpg} \href{http://codeforces.ru/profile/I_love_ilona}{Alex_KPR}: --- \textit{...начиная где-то с декартовых деревьев, FFT и так далее, вбивание и отладка кода становятся напрягающими и довольно занудными задачами...} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{А можно я придерусь к мелочи. Что делают в одном ряду по времени написания декартово дерево и FFT?} \includegraphics{https://static.e-olymp.com/content/5a/5a455f8d436fd6f1fa92bfb353bad4978d280e9f.jpg} \href{http://codeforces.ru/profile/I_love_ilona}{Alex_KPR}: --- \textit{это первое, что пришло в голову, где нужно много писать и есть где накосячить} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{Я же сказал: придираюсь к мелочам. Просто на мой взгляд рядом поставлены вещи, одна из которых несравнимо легче по написанию} \includegraphics{https://static.e-olymp.com/content/28/284cc1a5c3b121d515e3f20770dc84616d7160b6.jpg} \href{http://codeforces.ru/profile/homo_sapiens}{homo_sapiens}: --- \textit{Полностью согласен Фурье пишется вдвое может даже втрое быстрее чем дерево (но его обычно пихать надо руками и ногами)} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{Я имел ввиду с точностью наоборот. Все таки очень специфичная тема}. \includegraphics{https://static.e-olymp.com/content/28/284cc1a5c3b121d515e3f20770dc84616d7160b6.jpg} \href{http://codeforces.ru/profile/homo_sapiens}{homo_sapiens}: --- \textit{Видимо и правда на вкус и цвет}... Прийшов час дізнатись, що ж простіше. Вам пропонується дві послідовності з \textbf{N} цілих чисел \{\textbf{x_i}\} та \{\textbf{y_i}\}. Якщо вам більше подобається FFT, уявіть, що це коефіцієнти двох многочленів: \includegraphics{https://static.e-olymp.com/content/ee/ee9676608e69e38f86f1dbce3b0209cff58de0cc.jpg} Знайдіть коефіцієнти многочлена \textbf{P(z)·Q(z)}. Якщо ж вам більше подобаються Декартові дерева, уявіть, що \{\textbf{x_i}\} --- ключі, а \{\textbf{y_i}\} --- приорітети. Побудуйте Декартове дерево шляхом вставки у нього послідовно усіх \textbf{N} елементів (\textbf{x_i}, \textbf{y_i}). Після кожної вставки виводьте висоту отриманого дерева. Висота дерева --- кількість ребер на найдовшому шляху від довільної вершини до кореня. Для тих, хто обрав FFT, нагадаємо, що Декартове дерево --- це двійкове дерево пошуку за ключами, які містяться у вершинах (\textbf{x_i}). І одночасно куча за приорітетами в вершинах (\textbf{y_i}). Тобто, для кожної вершини дерева виконується властивість, що усі вершини з лівого піддерева мають ключі менші, ніж у даній вершині, а усі вершини з правого піддерева --- більші. А також приорітет даної вершини більше приорітета її синів. Незалежно від того, що ж ви вибрали, автор переконливо просить не викорстовувати у цій задачі \textit{prewritten code}. \InputFile У першому рядку число \textbf{N}. У другому рядку \textbf{N} різних цілих чисел --- \{\textbf{x_i}\}. У треому рядку \textbf{N} різних цілих чисел --- послідовність \{\textbf{y_i}\}. \OutputFile Якщо ви вибрали FFT, то виведіть \textbf{2N-1} цілих чисел --- коефіцієнти результуючого многочлена. Якщо Декартове дерево, то \textbf{N} цілих чисел --- висоти дерева після вставки у нього кожної вершини. Взагалі, ви можете вивести і те, і те, але тоді обидва результати будуть перевірятись на коректність. \textbf{Обмеження} \textbf{1} ≤ \textbf{N} ≤ \textbf{50000} \textbf{1} ≤ \textbf{x_i} ≤ \textbf{50000} \textbf{1} ≤ \textbf{y_i} ≤ \textbf{50000} Гарантується, що висота дерева не перевищить \textbf{50}.