409655: GYM103660 H Distance

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<l:dist(l,r,x)=l-x$$$
• If $$$l\le x\le r:dist(l,r,x)=0$$$
• If $$$r<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.

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 $$$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$$$.

3
1 3
6 8
6 8

0
3
3