H-Distance_第十九届浙大城市学院程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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  --- the number of pairs.
Then  lines follow, each line contains two integers  --- the -th pair you are given.

输出描述:

Output  lines, the -th line contains a single integer, which means the minimum value of . You can choose different  for different .

示例1

输入

复制

输出

复制

0
3
3