H. Distance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hile find a function $$$dist$$$ to calculate the distance from a point to an interval. For integer $$$l,r,x(l\le r)$$$, we define $$$dist(l,r,x)$$$ as follows.

  • If $$$x \lt l:dist(l,r,x)=l-x$$$
  • If $$$l\le x\le r:dist(l,r,x)=0$$$
  • If $$$r \lt x:dist(l,r,x)=x-r$$$

You are given $$$n$$$ pairs of integers, the $$$i$$$-th of which is $$$(l_i,r_i)$$$. It is guaranteed that $$$l_i \le r_i$$$ for all $$$i$$$. For each $$$k=1,2,...,n$$$, solve the following problem.

  • Choose an integer $$$x$$$ arbitrarily to minimize $$$\sum_{i=1}^{k}dist(l_i,r_i,x)$$$, output the minimum value.
Input

The first line contains a single integer $$$n(1 \le n \le 2\times 10^5)$$$ — the number of pairs.

Then $$$n$$$ lines follow, each line contains two integers $$$l_i,r_i(-10^9\le l_i\le r_i\le 10^9)$$$ — the $$$i$$$-th pair you are given.

Output

Output $$$n$$$ lines, the $$$k$$$-th line contains a single integer, which means the minimum value of $$$\sum_{i=1}^{k}dist(l_i,r_i,x)$$$. You can choose different $$$x$$$ for different $$$k$$$.

Example
Input
3
1 3
6 8
6 8
Output
0
3
3