AtCoDeer the deer found N rectangle lying on the table, each with height 1. If we consider the surface of the desk as a two-dimensional plane, the i-th rectangle i(1≤i≤N) covers the vertical range of [i-1,i] and the horizontal range of [l_i,r_i], as shown in the following figure:

<image>

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected. For each rectangle, the cost to move it horizontally by a distance of x, is x. Find the minimum cost to achieve connectivity. It can be proved that this value is always an integer under the constraints of the problem.

Constraints

* All input values are integers.
* 1≤N≤10^5
* 1≤l_i<r_i≤10^9

Input

The input is given from Standard Input in the following format:


N
l_1 r_1
l_2 r_2
:
l_N r_N


Output

Print the minimum cost to achieve connectivity.

Examples

Input

3
1 3
5 7
1 3


Output

2


Input

3
2 5
4 6
1 4


Output

0


Input

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000


Output

1999999680


Input

5
123456 789012
123 456
12 345678901
123456 789012
1 23


Output

246433


Input

1
1 400


Output

0
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>
#include <random>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
mt19937 rnd(123);
const ll INF = 2e9 + 1000;

struct node {
	node *l, *r;
	ll x, d, sum;
	ll dx;
	int y;
	node() {
		l = r = 0;
		x = d = sum = dx = 0;
		y = rnd();
	}
};

void push(node *v) {
	if (!v || !v->dx)
		return;
	if (v->l) {
		v->l->dx += v->dx;
		v->l->x += v->dx;
	}
	if (v->r) {
		v->r->dx += v->dx;
		v->r->x += v->dx;
	}
	v->dx = 0;
}

void upd(node *v) {
	if (!v)
		return;
	v->sum = v->d;
	if (v->l)
		v->sum += v->l->sum;
	if (v->r)
		v->sum += v->r->sum;
}

node *merge(node *l, node *r) {
	if (!l)
		return r;
	if (!r)
		return l;
	if (l->y > r->y) {
		push(l);
		l->r = merge(l->r, r);
		upd(l);
		return l;
	}
	else {
		push(r);
		r->l = merge(l, r->l);
		upd(r);
		return r;
	}
}

void split(node *v, ll x, node *&l, node *&r) {
	if (!v) {
		l = r = 0;
		return;
	}
	if (v->x >= x) {
		push(v);
		split(v->l, x, l, v->l);
		upd(v);
		r = v;
	}
	else {
		push(v);
		split(v->r, x, v->r, r);
		upd(v);
		l = v;
	}
}

ll find(node *v, ll now) {
	push(v);
	if (v->l && v->l->sum + now > 0)
		return find(v->l, now);
	if (v->l)
		now += v->l->sum;
	if (now + v->d > 0)
		return v->x;
	else
		now += v->d;
	return find(v->r, now);
}
ll gpnt = 0;
ll gtmp = 0;

node *root;

void add(ll x) {
	gtmp += abs(x - gpnt);
	node *tmp = root;
	while (tmp->l)
		tmp->sum -= 1, tmp = tmp->l;
	tmp->sum -= 1;
	tmp->d -= 1;
	node *l, *r, *m;
	split(root, x, l, r);
	split(r, x + 1, m, r);
	if (m) {
		m->d += 2;
		m->sum += 2;
	}
	else {
		m = new node();
		m->x = x;
		m->d = 2;
		m->sum = 2;
	}
	root = merge(l, merge(m, r));
}

void diva(ll l1, ll l2) {
	gpnt -= l1;
	ll x = find(root, 0);
	node *l, *r;
	node *tmp;
	split(root, x, l, r);
	if (l)
		l->dx -= l1, l->x -= l1;
	if (r)
		r->dx += l2, r->x += l2;
	if ((l ? l->sum : 0) != 0) {
		ll k = (l ? l->sum : 0);
		tmp = new node();
		tmp->x = x - l1;
		tmp->d = tmp->sum = -k;
		l = merge(l, tmp);
		tmp = r;
		while (tmp->l) {
			tmp->sum += k;
			tmp = tmp->l;
		}
		tmp->sum += k;
		tmp->d += k;
	}
	root = merge(l, r);
}

ll gans = 0;

void dfs1(node *v, ll x) {
	push(v);
	if (v->x < x)
		gans += v->d * (x - v->x);
	if (v->l)
		dfs1(v->l, x);
	if (v->r)
		dfs1(v->r, x);
}

ll getans() {
	ll x = find(root, 0);
	dfs1(root, x);
	return gans;
}

int n;
ll l[120000];
ll r[120000];

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		scanf("%lld%lld", l + i, r + i);
	root = new node();
	add(l[0]);
	for (int i = 1; i < n; ++i) {
		ll len1 = r[i - 1] - l[i - 1];
		ll len2 = r[i] - l[i];
		diva(len2, len1);
		add(l[i]);
	}
	cout << gtmp + getans() << "\n";
	return 0;
}


