Roy and Biv have a set of n points on the infinite number line.

Each point has one of 3 colors: red, green, or blue.

Roy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.

They want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).

However, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.

Therefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).

Help them compute the minimum cost way to choose edges to satisfy the above constraints.


-----Input-----

The first line will contain an integer n (1 ≤ n ≤ 300 000), the number of points.

The next n lines will contain two tokens p_{i} and c_{i} (p_{i} is an integer, 1 ≤ p_{i} ≤ 10^9, c_{i} is a uppercase English letter 'R', 'G' or 'B'), denoting the position of the i-th point and the color of the i-th point. 'R' means red, 'G' denotes green, and 'B' means blue. The positions will be in strictly increasing order.


-----Output-----

Print a single integer, the minimum cost way to solve the problem.


-----Examples-----
Input
4
1 G
5 R
10 B
15 G

Output
23

Input
4
1 G
2 R
3 B
10 G

Output
12



-----Note-----

In the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.

Difficulty: VERY_HARD
Tags: Graph algorithms

Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
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 == 'G':
		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 += max(g[i + 1] - g[i], min(a1 - mr - mb, a2))
print(str(ans))


k = int(input())
(t, a, b, m, n, o, d, e, s, x, y, z, l) = 13 * [0]
for i in range(k):
	c = input().split(' ')
	f = int(c[0])
	if c[1] == 'G':
		if o < 1:
			z = f
		if t:
			if m > 0:
				d = max(d, f - m)
			if n > 0:
				e = max(e, f - n)
			s += min(2 * (f - o), 3 * (f - o) - d - e)
		(d, e, a, b) = 4 * [0]
		(m, n, o) = 3 * [f]
		t = 1
		l += 1
	if c[1] == 'R':
		a += 1
		if m < 1:
			x = f
		if m > 0 and t:
			d = max(d, f - m)
		m = f
	if c[1] == 'B':
		b += 1
		if n < 1:
			y = f
		if n > 0 and t:
			e = max(e, f - n)
		n = f
if l > 0:
	if a > 0:
		s += m - o
	if b > 0:
		s += n - o
	if x > 0:
		s += z - x
	if y > 0:
		s += z - y
else:
	s = m - x + n - y
print(s)


from sys import stdin, stdout
n = int(stdin.readline())
challengers = []
for i in range(n):
	s = stdin.readline().strip().split()
	challengers.append((int(s[0]), s[1]))
challengers.sort()
G = []
R = []
B = []
for i in range(n):
	v = challengers[i]
	if v[1] == 'G':
		G.append(i)
	elif v[1] == 'R':
		R.append(i)
	else:
		B.append(i)
test = []
for v in challengers:
	test.append(v[0])
challengers = test[:]
ans = 0
if len(G):
	(indr, indb) = (0, 0)
	for i in range(len(G) - 1):
		while indr < len(R) and R[indr] < G[i]:
			indr += 1
		while indb < len(B) and B[indb] < G[i]:
			indb += 1
		(mxr, mxb) = (0, 0)
		previous = G[i]
		(used1, used2) = (0, 0)
		while indr < len(R) and R[indr] < G[i + 1]:
			mxr = max(mxr, challengers[R[indr]] - challengers[previous])
			previous = R[indr]
			indr += 1
			used1 = 1
		mxr = max(mxr, -challengers[previous] + challengers[G[i + 1]])
		previous = G[i]
		while indb < len(B) and B[indb] < G[i + 1]:
			mxb = max(mxb, challengers[B[indb]] - challengers[previous])
			previous = B[indb]
			indb += 1
			used2 = 1
		mxb = max(mxb, -challengers[previous] + challengers[G[i + 1]])
		d = challengers[G[i + 1]] - challengers[G[i]]
		ans += min(2 * d, 3 * d - mxb - mxr)
	if R and R[0] < G[0]:
		for i in range(1, len(R)):
			if R[i] > G[0]:
				ans += challengers[G[0]] - challengers[R[i - 1]]
				break
			else:
				ans += challengers[R[i]] - challengers[R[i - 1]]
		else:
			ans += challengers[G[0]] - challengers[R[-1]]
	if B and B[0] < G[0]:
		for i in range(1, len(B)):
			if B[i] > G[0]:
				ans += challengers[G[0]] - challengers[B[i - 1]]
				break
			else:
				ans += challengers[B[i]] - challengers[B[i - 1]]
		else:
			ans += challengers[G[0]] - challengers[B[-1]]
	label = 0
	if R and R[-1] > G[-1]:
		for i in range(len(R)):
			if not label and R[i] > G[-1]:
				ans += challengers[R[i]] - challengers[G[-1]]
				label = 1
			elif R[i] > G[-1]:
				ans += challengers[R[i]] - challengers[R[i - 1]]
	label = 0
	if B and B[-1] > G[-1]:
		for i in range(len(B)):
			if not label and B[i] > G[-1]:
				ans += challengers[B[i]] - challengers[G[-1]]
				label = 1
			elif B[i] > G[-1]:
				ans += challengers[B[i]] - challengers[B[i - 1]]
else:
	for i in range(1, len(R)):
		ans += challengers[R[i]] - challengers[R[i - 1]]
	for i in range(1, len(B)):
		ans += challengers[B[i]] - challengers[B[i - 1]]
stdout.write(str(ans))


n = int(input())
(nfirst, rc, bc, memr, memb, memg, dr, db, s, rl, bl, gl, lg) = 13 * [0]
for i in range(n):
	a = input().split(' ')
	if a[1] == 'G':
		if memg == 0:
			gl = int(a[0])
		if nfirst:
			if memr > 0:
				dr = max(dr, int(a[0]) - memr)
			if memb > 0:
				db = max(db, int(a[0]) - memb)
			s += min(2 * (int(a[0]) - memg), 3 * (int(a[0]) - memg) - dr - db)
		(dr, db, rc, bc) = 4 * [0]
		(memr, memb, memg) = 3 * [int(a[0])]
		nfirst = True
		lg += 1
	elif a[1] == 'R':
		rc += 1
		if memr == 0:
			rl = int(a[0])
		if memr > 0 and nfirst:
			dr = max(dr, int(a[0]) - memr)
		memr = int(a[0])
	elif a[1] == 'B':
		bc += 1
		if memb == 0:
			bl = int(a[0])
		if memb > 0 and nfirst:
			db = max(db, int(a[0]) - memb)
		memb = int(a[0])
if lg > 0:
	if rc > 0:
		s += memr - memg
	if bc > 0:
		s += memb - memg
	if rl > 0:
		s += gl - rl
	if bl > 0:
		s += gl - bl
else:
	s += memr - rl + memb - bl
print(s)


import sys
n = int(input())
pos = []
ind = 0
inp = [s for line in sys.stdin.readlines() for s in line.split()]
color = []
costs = 0
reds = []
greens = []
blues = []
for i in range(n):
	(a, b) = (inp[ind], inp[ind + 1])
	ind += 2
	pos.append(int(a))
	color.append(b)
	if b == 'R':
		reds.append(i)
	elif b == 'G':
		greens.append(i)
	else:
		blues.append(i)
if len(greens) == 0:
	if len(reds) > 0:
		a = reds[0]
		b = reds[-1]
		costs += pos[b] - pos[a]
	if len(blues) > 0:
		a = blues[0]
		b = blues[-1]
		costs += pos[b] - pos[a]
	print(costs)
	sys.exit()
first_g = greens[0]
last_g = greens[-1]
if len(blues) > 0 and blues[0] <= first_g:
	costs += pos[first_g] - pos[blues[0]]
if len(reds) > 0 and reds[0] <= first_g:
	costs += pos[first_g] - pos[reds[0]]
if len(blues) > 0 and blues[-1] >= last_g:
	costs += pos[blues[-1]] - pos[last_g]
if len(reds) > 0 and reds[-1] >= last_g:
	costs += pos[reds[-1]] - pos[last_g]
i = first_g
while True:
	j = i + 1
	REDS = [i]
	BLUES = [i]
	while j < n and color[j] != 'G':
		if color[j] == 'R':
			REDS.append(j)
		else:
			BLUES.append(j)
		j += 1
	if j >= n:
		break
	REDS.append(j)
	BLUES.append(j)
	best_r = 0
	for ind in range(len(REDS) - 1):
		a = REDS[ind]
		b = REDS[ind + 1]
		best_r = max(best_r, pos[b] - pos[a])
	best_b = 0
	for ind in range(len(BLUES) - 1):
		a = BLUES[ind]
		b = BLUES[ind + 1]
		best_b = max(best_b, pos[b] - pos[a])
	costs += min(2 * (pos[j] - pos[i]), 3 * (pos[j] - pos[i]) - best_r - best_b)
	i = j
print(costs)


n = int(input())
r = 0
g = 0
b = 0
maxR = 0
maxB = 0
maxG = 0
minCost = 0
for i in range(n):
	(p, c) = input().split(' ')
	p = int(p)
	if c == 'R' or c == 'G':
		if r:
			minCost += p - r
			maxR = max(maxR, p - r)
		r = p
	if c == 'B' or c == 'G':
		if b:
			minCost += p - b
			maxB = max(maxB, p - b)
		b = p
	if c == 'G':
		if g:
			minCost += min(0, p - g - maxR - maxB)
		g = p
		maxR = 0
		maxB = 0
print(minCost)


n = int(input())
g = []
r = []
b = []
lr = 0
lb = 0
lg = 0
for i in range(n):
	a = input().split(' ')
	if a[1] == 'G':
		g.append(int(a[0]))
		lg += 1
	if a[1] == 'R':
		r.append(int(a[0]))
		lr += 1
	if a[1] == 'B':
		b.append(int(a[0]))
		lb += 1
g = g[::-1]
r = r[::-1]
b = b[::-1]
s = 0
if lg > 0:
	for i in range(lg + 1):
		if i == 0:
			ps = 0
			if lr > 0:
				if r[lr - 1] < g[lg - 1]:
					ps += g[lg - 1] - r[lr - 1]
					while r[lr - 1] < g[lg - 1]:
						lr -= 1
						if lr == 0:
							break
			if lb > 0:
				if b[lb - 1] < g[lg - 1]:
					ps += g[lg - 1] - b[lb - 1]
					while b[lb - 1] < g[lg - 1]:
						lb -= 1
						if lb == 0:
							break
			s += ps
		elif i == lg:
			ps = 0
			if lr > 0:
				ps += r[0] - g[0]
			if lb > 0:
				ps += b[0] - g[0]
			s += ps
		else:
			ps = 0
			d = g[lg - i - 1] - g[lg - i]
			rin = False
			blin = False
			if lr > 0:
				if r[lr - 1] < g[lg - i - 1]:
					rin = True
					mdr = r[lr - 1] - g[lg - i]
					if lr > 1:
						while r[lr - 2] < g[lg - i - 1]:
							mdr = max(mdr, r[lr - 2] - r[lr - 1])
							lr -= 1
							if lr == 1:
								break
					mdr = max(mdr, g[lg - i - 1] - r[lr - 1])
					lr -= 1
			if lb > 0:
				if b[lb - 1] < g[lg - i - 1]:
					blin = True
					mdb = b[lb - 1] - g[lg - i]
					if lb > 1:
						while b[lb - 2] < g[lg - i - 1]:
							mdb = max(mdb, b[lb - 2] - b[lb - 1])
							lb -= 1
							if lb == 1:
								break
					mdb = max(mdb, g[lg - i - 1] - b[lb - 1])
					lb -= 1
			if blin and rin:
				ps += min(2 * d, 3 * d - mdr - mdb)
			else:
				ps += d
				if blin:
					ps += d - mdb
				elif rin:
					ps += d - mdr
			s += ps
else:
	if lr > 0:
		s += r[0] - r[-1]
	if lb > 0:
		s += b[0] - b[-1]
print(s)


n = int(input())
(min_red, max_red) = (-1, -1)
(min_blue, max_blue) = (-1, -1)
(left_green, right_green) = (-1, -1)
a = []
ans = 0
(last_r, last_b, last_g) = (-1, -1, -1)
r_edges = []
b_edges = []
g_edges = []
for i in range(n):
	(p, c) = input().split()
	p = int(p)
	if c == 'R' or c == 'G':
		if last_r != -1:
			r_edges.append(p - last_r)
		last_r = p
	if c == 'B' or c == 'G':
		if last_b != -1:
			b_edges.append(p - last_b)
		last_b = p
	if c == 'G':
		ans += sum(r_edges) + sum(b_edges)
		if len(r_edges) > 0:
			max_red = max(r_edges)
		if len(b_edges) > 0:
			max_blue = max(b_edges)
		if last_g != -1:
			if p - last_g < max_red + max_blue:
				ans += p - last_g
				ans -= max_red + max_blue
		r_edges = []
		b_edges = []
		last_g = p
ans += sum(r_edges) + sum(b_edges)
print(ans)


def F1():
	n = int(input())
	ans = 0
	allc = 0
	bigr = 0
	bigb = 0
	lastr = -1
	lastb = -1
	lastg = -(1 << 60)
	for i in range(n):
		x = input().split()
		(pos, col) = (int(x[0]), x[1])
		if col == 'R' or col == 'G':
			if lastr != -1:
				bigr = max(bigr, pos - lastr)
				allc += pos - lastr
			lastr = pos
		if col == 'B' or col == 'G':
			if lastb != -1:
				bigb = max(bigb, pos - lastb)
				allc += pos - lastb
			lastb = pos
		if col == 'G':
			ans += allc + min(0, -bigr - bigb + pos - lastg)
			lastr = lastb = lastg = pos
			bigr = bigb = allc = 0
	ans += allc
	print(ans)
F1()


n = int(input())
(R, G, B) = (0, 0, 0)
(maxR, maxG, maxB) = (0, 0, 0)
Cost = 0
for i in range(n):
	temp_input = input().split(' ')
	value = int(temp_input[0])
	choice = temp_input[1]
	if choice == 'R' or choice == 'G':
		if R:
			Cost += value - R
			maxR = max(maxR, value - R)
		R = value
	if choice == 'B' or choice == 'G':
		if B:
			Cost += value - B
			maxB = max(maxB, value - B)
		B = value
	if choice == 'G':
		if G:
			Cost += min(0, value - G - maxR - maxB)
		G = value
		maxR = 0
		maxB = 0
print(Cost)


import sys
n = int(sys.stdin.readline().rstrip())
locations = {'R': [], 'G': [], 'B': []}
for i in range(n):
	(x, c) = sys.stdin.readline().rstrip().split()
	locations[c].append(int(x))

def solve(locations):
	count = 0
	rPtr = 0
	bPtr = 0
	gPtr = 0
	if len(locations['G']) == 0:
		if len(locations['R']):
			count += locations['R'][-1] - locations['R'][0]
		if len(locations['B']):
			count += locations['B'][-1] - locations['B'][0]
		return count
	while len(locations['G']) > gPtr:
		if len(locations['R']) > rPtr and locations['G'][gPtr] > locations['R'][rPtr]:
			count += locations['G'][gPtr] - locations['R'][rPtr]
			while len(locations['R']) > rPtr and locations['G'][gPtr] > locations['R'][rPtr]:
				rPtr += 1
		if len(locations['B']) > bPtr and locations['G'][gPtr] > locations['B'][bPtr]:
			count += locations['G'][gPtr] - locations['B'][bPtr]
			while len(locations['B']) > bPtr and locations['G'][gPtr] > locations['B'][bPtr]:
				bPtr += 1
		if len(locations['G']) == gPtr + 1:
			if len(locations['R']) > rPtr:
				count += locations['R'][-1] - locations['G'][gPtr]
			if len(locations['B']) > bPtr:
				count += locations['B'][-1] - locations['G'][gPtr]
			return count
		if len(locations['G']) > gPtr + 1:
			prevR = locations['G'][gPtr]
			maxRd = 0
			while len(locations['R']) > rPtr:
				if locations['R'][rPtr] < locations['G'][gPtr + 1]:
					maxRd = max(maxRd, locations['R'][rPtr] - prevR)
					prevR = locations['R'][rPtr]
					rPtr += 1
				else:
					break
			maxRd = max(maxRd, locations['G'][gPtr + 1] - prevR)
			prevB = locations['G'][gPtr]
			maxBd = 0
			while len(locations['B']) > bPtr:
				if locations['B'][bPtr] < locations['G'][gPtr + 1]:
					maxBd = max(maxBd, locations['B'][bPtr] - prevB)
					prevB = locations['B'][bPtr]
					bPtr += 1
				else:
					break
			maxBd = max(maxBd, locations['G'][gPtr + 1] - prevB)
			count += min(2 * (locations['G'][gPtr + 1] - locations['G'][gPtr]), 3 * (locations['G'][gPtr + 1] - locations['G'][gPtr]) - maxRd - maxBd)
			gPtr += 1
	return count
print(solve(locations))


r = g = b = 0
R = G = B = 0
s = u = v = 0
f = lambda k: k if k else n
for i in range(int(input())):
	(q, c) = input().split()
	n = int(q)
	if c in 'RG':
		(r, R, u) = (f(r), n, max(u, n - R))
	if c in 'BG':
		(b, B, v) = (f(b), n, max(v, n - B))
	if c == 'G':
		if g:
			s -= max(u + v, n - G)
		(g, G, u, v) = (f(g), n, 0, 0)
print(s + R - r + G - g + B - b)


n = int(input())
result = 0
temp = 0
b_red = 0
b_blue = 0
final_red = -1
final_blue = -1
final_green = -(1 << 60)
for i in range(n):
	cost_colorList = input().split()
	cost = int(cost_colorList[0])
	color = cost_colorList[1]
	if color == 'R' or color == 'G':
		if final_red != -1:
			b_red = max(b_red, cost - final_red)
			temp += cost - final_red
		final_red = cost
	if color == 'B' or color == 'G':
		if final_blue != -1:
			b_blue = max(b_blue, cost - final_blue)
			temp += cost - final_blue
		final_blue = cost
	if color == 'G':
		result += temp + min(0, -b_red - b_blue + cost - final_green)
		final_red = final_blue = final_green = cost
		b_red = b_blue = temp = 0
result += temp
print(result)