409029: GYM103416 I Restricted Track

We have a track that is infinite in one direction.

At the begging of the track, we have a car with an initial speed of $$$v=0$$$ m/s. Also, the car has an acceleration of $$$a$$$ m$$$/s^2$$$, which we can change at any moment of time to a value in the range [1, -1] m$$$/s^2$$$. The speed of the car can reach any value in the range (-$$$\infty$$$, $$$\infty$$$) m/s

We are given $$$n$$$ requests. In each request, a new restriction $$$(t, r)$$$ is added: At the moment when $$$t$$$ seconds have passed from the start of the race, the speed of the car should satisfy $$$v \leq r$$$ (at that exact moment).

After each request, you need to print the maximum distance that the car can reach at the moment when all restrictions are passed.

The first line of the input contains a single integer $$$ n $$$ ($$$ 1 \leq n \leq 2 00 000 $$$) — the number of requests.

Each of the next n lines contains two integers $$$ t_i $$$, $$$ r_i $$$ ($$$ 1 \leq t_i \leq 10 ^ 9 $$$), ($$$ 0 \leq r_i \leq 10 ^ 9 $$$) - a moment in time, and a speed limit.

For each request, print the answer to how far the car can go at the moment when it passes all the restrictions. The absolute error of your answer must not exceed ($$$10^{-6}$$$).

3
1 3
3 3
1 0

0.500000000
4.500000000
2.250000000