Interactive

Alex_KPR: — ...starting somewhere from treaps, FFT, and so on, writing and debugging code becomes a strenuous and rather tedious task...

Kunyavsky: — May I nitpick? Why are you mentioning writing a treap and FFT in the same timescale?

Alex_KPR: — That's just the first thing that came to mind, where writing much code and making mistakes is likely.

Kunyavsky: — I've said: I'm nitpicking. In my opinion, these are two things, one of which is much easier to write than the other.

homo_sapiens: — I absolutely agree. In my experience, FFT can be coded two or even three times faster than a treap (although it often has to be pushed and prodded by hand).

Kunyavsky: — I meant quite the opposite. It is, after all, a very specialized topic.

homo_sapiens: — Apparently, it comes down to a matter of taste...

It's time to find out what is simpler.

Two sequences of $N$ integers are given: \{x_i\} and \{y_i\}.

If you prefer FFT, imagine these sequences are the coefficients of two polynomials:

Find the coefficients of the polynomial P(z) \cdot Q(z).

Alternatively, if you prefer treaps, imagine that \{x_i\} are keys and \{y_i\} are priorities. Build a treap by inserting all $N$ elements (x_i, y_i) in order. After each insertion, output the height of the resulting treap.

For those choosing FFT, recall that a treap is a binary search tree by keys (x_i), and at the same time a heap by priorities (y_i). That is, for every node in the tree, all nodes in the left subtree have smaller keys than in the node, and all nodes in the right subtree have greater keys; also, the priorities of the children are less than the priority of the node.

Regardless of your choice, the author strongly requests that you do not use prewritten code in this problem.