The cities of Byteland and Berland are located on the axis $Ox$. In addition, on this axis there are also disputed cities, which belong to each of the countries in their opinion. Thus, on the line $Ox$ there are three types of cities:  the cities of Byteland,  the cities of Berland,  disputed cities. 

Recently, the project BNET has been launched — a computer network of a new generation. Now the task of the both countries is to connect the cities so that the network of this country is connected.

The countries agreed to connect the pairs of cities with BNET cables in such a way that:  If you look at the only cities of Byteland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables,  If you look at the only cities of Berland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables. 

Thus, it is necessary to choose a set of pairs of cities to connect by cables in such a way that both conditions are satisfied simultaneously. Cables allow bi-directional data transfer. Each cable connects exactly two distinct cities.

The cost of laying a cable from one city to another is equal to the distance between them. Find the minimum total cost of laying a set of cables so that two subsets of cities (Byteland and disputed cities, Berland and disputed cities) are connected.

Each city is a point on the line $Ox$. It is technically possible to connect the cities $a$ and $b$ with a cable so that the city $c$ ($a < c < b$) is not connected to this cable, where $a$, $b$ and $c$ are simultaneously coordinates of the cities $a$, $b$ and $c$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^{5}$) — the number of cities.

The following $n$ lines contains an integer $x_i$ and the letter $c_i$ ($-10^{9} \le x_i \le 10^{9}$) — the coordinate of the city and its type. If the city belongs to Byteland, $c_i$ equals to 'B'. If the city belongs to Berland, $c_i$ equals to «R». If the city is disputed, $c_i$ equals to 'P'. 

All cities have distinct coordinates. Guaranteed, that the cities are given in the increasing order of their coordinates.


-----Output-----

Print the minimal total length of such set of cables, that if we delete all Berland cities ($c_i$='R'), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables. Similarly, if we delete all Byteland cities ($c_i$='B'), it will be possible to find a way from any remaining city to any other remaining city, moving only by cables.


-----Examples-----
Input
4
-5 R
0 P
3 P
7 B

Output
12

Input
5
10 R
14 B
16 B
21 R
32 R

Output
24



-----Note-----

In the first example, you should connect the first city with the second, the second with the third, and the third with the fourth. The total length of the cables will be $5 + 3 + 4 = 12$.

In the second example there are no disputed cities, so you need to connect all the neighboring cities of Byteland and all the neighboring cities of Berland. The cities of Berland have coordinates $10, 21, 32$, so to connect them you need two cables of length $11$ and $11$. The cities of Byteland have coordinates $14$ and $16$, so to connect them you need one cable of length $2$. Thus, the total length of all cables is $11 + 11 + 2 = 24$.

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Constructive algorithms


Solutions:
def solve(length, cities):
	result = 0
	lastP = None
	lastB = None
	lastR = None
	maxB = 0
	maxR = 0
	for (idx, city) in enumerate(cities):
		(i, code) = city
		if code == 'B':
			if lastB != None:
				result += abs(i - lastB)
				maxB = max(maxB, abs(i - lastB))
			lastB = i
		if code == 'R':
			if lastR != None:
				result += abs(i - lastR)
				maxR = max(maxR, abs(i - lastR))
			lastR = i
		if code == 'P':
			if lastB != None:
				result += abs(i - lastB)
				maxB = max(maxB, abs(i - lastB))
			if lastR != None:
				result += abs(i - lastR)
				maxR = max(maxR, abs(i - lastR))
			if lastP != None:
				result += min(0, abs(i - lastP) - maxB - maxR)
			maxB = 0
			maxR = 0
			lastB = i
			lastR = i
			lastP = i
	return result
length = int(input())
cities = []
for i in range(length):
	data = input().split(' ')
	cities.append((int(data[0]), data[1]))
result = solve(length, cities)
print(result)


def inpmap():
	return map(int, input().split())
n = int(input())
(b, r, p) = (None, None, None)
res = 0
mr = -1
mb = -1
for i in range(n):
	(ix, t) = input().split()
	ix = int(ix)
	if t != 'R':
		if b is not None:
			res += ix - b
			mb = max(mb, ix - b)
		b = ix
	if t != 'B':
		if r is not None:
			res += ix - r
			mr = max(mr, ix - r)
		r = ix
	if t == 'P':
		if p is not None:
			if ix - p < mr + mb:
				res -= mr + mb - (ix - p)
		p = ix
		mr = mb = 0
print(res)


from sys import exit, stdin, stdout
(input, print) = (stdin.readline, stdout.write)
n = int(input())
(r, g, b) = ([], [], [])
ans = 0
for i in range(n):
	(x, t) = [i for i in input().split()]
	x = int(x)
	if t == 'P':
		g.append(x)
	elif t == 'R':
		r.append(x)
	else:
		b.append(x)
if len(g) == 0:
	if len(r):
		ans += r[-1] - r[0]
	if len(b):
		ans += b[-1] - b[0]
	print(str(ans))
	exit(0)
if not len(r):
	r.append(g[0])
if not len(b):
	b.append(g[0])
if r[0] < g[0]:
	ans += g[0] - r[0]
if b[0] < g[0]:
	ans += g[0] - b[0]
if r[-1] > g[-1]:
	ans += r[-1] - g[-1]
if b[-1] > g[-1]:
	ans += b[-1] - g[-1]
(bi, ri) = (0, 0)
for i in range(len(g) - 1):
	while bi < len(b) - 1 and b[bi] < g[i]:
		bi += 1
	while ri < len(r) - 1 and r[ri] < g[i]:
		ri += 1
	(a1, a2) = ((g[i + 1] - g[i]) * 3, (g[i + 1] - g[i]) * 2)
	(mr, mb, cbi, cri) = (r[ri] - g[i], b[bi] - g[i], bi, ri)
	while cbi + 1 < len(b) and b[cbi + 1] < g[i + 1]:
		mb = max(mb, b[cbi + 1] - b[cbi])
		cbi += 1
	mb = max(mb, g[i + 1] - b[cbi])
	while cri + 1 < len(r) and r[cri + 1] < g[i + 1]:
		mr = max(mr, r[cri + 1] - r[cri])
		cri += 1
	mr = max(mr, g[i + 1] - r[cri])
	if b[bi] < g[i] or b[bi] > g[i + 1]:
		a2 = 100000000000000
		a1 -= g[i + 1] - g[i]
		mb = 0
	if r[ri] < g[i] or r[ri] > g[i + 1]:
		a2 = 100000000000000
		a1 -= g[i + 1] - g[i]
		mr = 0
	ans += min(a1 - mr - mb, a2)
print(str(ans))


n = int(input())
(b, r, p) = (None, None, None)
ans = 0
mr = -1
mb = -1
for i in range(n):
	(ix, t) = input().split()
	ix = int(ix)
	if t != 'R':
		if b is not None:
			ans += ix - b
			mb = max(mb, ix - b)
		b = ix
	if t != 'B':
		if r is not None:
			ans += ix - r
			mr = max(mr, ix - r)
		r = ix
	if t == 'P':
		if p is not None:
			if ix - p < mr + mb:
				ans -= mr + mb - (ix - p)
		p = ix
		mr = mb = 0
print(ans)


n = int(input())
last_r = None
last_b = None
last_p = None
ans = 0
max_r = 0
max_b = 0
max_p = 0
for _ in range(n):
	s = input().split()
	x = int(s[0])
	c = s[1]
	if c == 'B':
		if last_b != None:
			ans += x - last_b
			max_b = max(max_b, x - last_b)
		last_b = x
	if c == 'R':
		if last_r != None:
			ans += x - last_r
			max_r = max(max_r, x - last_r)
		last_r = x
	if c == 'P':
		if last_b != None:
			ans += x - last_b
			max_b = max(max_b, x - last_b)
		last_b = x
		if last_r != None:
			ans += x - last_r
			max_r = max(max_r, x - last_r)
		last_r = x
		if last_p != None:
			new_ans = (x - last_p) * 3
			new_ans -= max_r
			new_ans -= max_b
			if new_ans < (x - last_p) * 2:
				ans -= (x - last_p) * 2 - new_ans
		last_p = x
		max_b = 0
		max_r = 0
print(ans)


import sys
n = int(sys.stdin.buffer.readline().decode('utf-8'))
(pos, type_) = ([0] * n, [''] * n)
for (i, (x, c)) in enumerate((line.decode('utf-8').split() for line in sys.stdin.buffer)):
	pos[i] = int(x)
	type_[i] = c
r_cnt = type_.count('R')
b_cnt = type_.count('B')
p_cnt = n - r_cnt - b_cnt
inf = 2100000000
if p_cnt == 0:
	(r_min, r_max) = (inf, inf)
	(b_min, b_max) = (inf, inf)
	for i in range(n):
		if type_[i] == 'R':
			r_min = min(pos[i], r_min)
			r_max = pos[i]
		else:
			b_min = min(pos[i], b_min)
			b_max = pos[i]
	print(r_max - r_min + b_max - b_min)
	exit()
p_index = [i for i in range(n) if type_[i] == 'P']
ans = 0
for c in 'RB':
	for i in range(p_index[0]):
		if type_[i] == c:
			ans += pos[p_index[0]] - pos[i]
			break
	for i in range(n - 1, p_index[-1], -1):
		if type_[i] == c:
			ans += pos[i] - pos[p_index[-1]]
			break
for (i, j) in zip(p_index, p_index[1:]):
	(r, b) = ([], [])
	r_prev = b_prev = pos[i]
	for k in range(i + 1, j):
		if type_[k] == 'R':
			r.append(pos[k] - r_prev)
			r_prev = pos[k]
		else:
			b.append(pos[k] - b_prev)
			b_prev = pos[k]
	r.append(pos[j] - r_prev)
	b.append(pos[j] - b_prev)
	r.sort()
	b.sort()
	ans += min(pos[j] - pos[i] + sum(r) - r[-1] + sum(b) - b[-1], sum(r) + sum(b))
print(ans)


M = 4 * 10 ** 9 + 1
n = int(input().strip())
f = lambda t: (int(t[0]), t[1])
xcis = [(-M, 'P')] + [f(input().strip().split()) for _ in range(n)] + [(M, 'P')]
iPs = [i for i in range(len(xcis)) if xcis[i][1] == 'P']
iRs = [i for i in range(len(xcis)) if xcis[i][1] == 'R']
iBs = [i for i in range(len(xcis)) if xcis[i][1] == 'B']
l = 0
for iiP in range(1, len(iPs)):
	iP0 = iPs[iiP - 1]
	iP1 = iPs[iiP]
	dRmax = 0
	dBmax = 0
	(xR, _) = xcis[iP0]
	(xB, _) = xcis[iP0]
	for i in range(iP0 + 1, iP1 + 1):
		(x, c) = xcis[i]
		if c in 'RP':
			dRmax = max(dRmax, x - xR)
			xR = x
		if c in 'BP':
			dBmax = max(dBmax, x - xB)
			xB = x
	d = xcis[iP1][0] - xcis[iP0][0]
	l += d + min(d, 2 * d - dBmax - dRmax)
	if iiP in [1, len(iPs) - 1]:
		l -= d
	iP0 = iP1
if len(iPs) == 2:
	l = 0 if len(iRs) < 2 else xcis[iRs[-1]][0] - xcis[iRs[0]][0]
	l += 0 if len(iBs) < 2 else xcis[iBs[-1]][0] - xcis[iBs[0]][0]
print(l)


rides = int(input())
franxx = []
Zero = []
Two = []
for i in range(rides):
	darling = input().split()
	if darling[1] == 'B':
		darling[1] = 1
	elif darling[1] == 'R':
		darling[1] = 2
	else:
		darling[1] = 3
	franxx.append((int(darling[0]), int(darling[1])))
love = 0
hiro = ['I love Zero Two', 'I love Darling']
for (zero, two) in franxx:
	if two == 3 or two == 1:
		if hiro[0] == 'I love Zero Two':
			Zero.append(0)
			hiro[0] = zero
		else:
			Zero.append(zero - hiro[0])
			love += zero - hiro[0]
			hiro[0] = zero
	if two == 3 or two == 2:
		if hiro[1] == 'I love Darling':
			Two.append(0)
			hiro[1] = zero
		else:
			Two.append(zero - hiro[1])
			love += zero - hiro[1]
			hiro[1] = zero
	if two == 1:
		Two.append(0)
	elif two == 2:
		Zero.append(0)
hiro = [-1, 0]
for ride in range(rides):
	if franxx[ride][1] == 3:
		if hiro[0] == -1:
			hiro[0] = ride
			hiro[1] = 0
		else:
			strelizia = [0, 0]
			if hiro[1] & 1 == 0:
				strelizia[0] = franxx[ride][0] - franxx[hiro[0]][0]
			if hiro[1] & 2 == 0:
				strelizia[1] = franxx[ride][0] - franxx[hiro[0]][0]
			for darling in range(hiro[0], ride):
				if hiro[1] & 1:
					strelizia[0] = max(strelizia[0], Zero[darling + 1])
				if hiro[1] & 2:
					strelizia[1] = max(strelizia[1], Two[darling + 1])
			if strelizia[0] + strelizia[1] - franxx[ride][0] + franxx[hiro[0]][0] > 0:
				love -= strelizia[0] + strelizia[1] - franxx[ride][0] + franxx[hiro[0]][0]
			hiro[0] = ride
			hiro[1] = 0
	else:
		hiro[1] |= franxx[ride][1]
print(love)