There will be a launch of a new, powerful and unusual collider very soon, which located along a straight line. n particles will be launched inside it. All of them are located in a straight line and there can not be two or more particles located in the same point. The coordinates of the particles coincide with the distance in meters from the center of the collider, x_{i} is the coordinate of the i-th particle and its position in the collider at the same time. All coordinates of particle positions are even integers.

You know the direction of each particle movement — it will move to the right or to the left after the collider's launch start. All particles begin to move simultaneously at the time of the collider's launch start. Each particle will move straight to the left or straight to the right with the constant speed of 1 meter per microsecond. The collider is big enough so particles can not leave it in the foreseeable time.

Write the program which finds the moment of the first collision of any two particles of the collider. In other words, find the number of microseconds before the first moment when any two particles are at the same point.


-----Input-----

The first line contains the positive integer n (1 ≤ n ≤ 200 000) — the number of particles. 

The second line contains n symbols "L" and "R". If the i-th symbol equals "L", then the i-th particle will move to the left, otherwise the i-th symbol equals "R" and the i-th particle will move to the right.

The third line contains the sequence of pairwise distinct even integers x_1, x_2, ..., x_{n} (0 ≤ x_{i} ≤ 10^9) — the coordinates of particles in the order from the left to the right. It is guaranteed that the coordinates of particles are given in the increasing order. 


-----Output-----

In the first line print the only integer — the first moment (in microseconds) when two particles are at the same point and there will be an explosion. 

Print the only integer -1, if the collision of particles doesn't happen. 


-----Examples-----
Input
4
RLRL
2 4 6 10

Output
1

Input
3
LLR
40 50 60

Output
-1



-----Note-----

In the first sample case the first explosion will happen in 1 microsecond because the particles number 1 and 2 will simultaneously be at the same point with the coordinate 3. 

In the second sample case there will be no explosion because there are no particles which will simultaneously be at the same point.

Difficulty: interview

Starter code:

Solutions:
import sys, math
n=int(input())
s=input()
z=list(map(int,input().split()))
best = 10**9
for i in range(len(s)-1):
    if s[i]=='R' and s[i+1]=='L':
        best=min(best, z[i+1]-(z[i]+z[i+1])//2)
if best != 10**9:
    print(best)
else:
    print(-1)


n = int(input())
s = input()
x = list(map(int, input().split()))
ans = float('inf')
last = None
for i in range(n):
    if s[i] == 'R':
        last = x[i]
    elif last != None:
        cur = (x[i] - last) // 2
        ans = min(ans, cur)
if ans == float('inf'):
    ans = -1
print(ans)


n = int(input())
s = input()
l = list(map(int, input().split()))
ans = 10 ** 18
last_r = -1
for i in range(len(l)):
    if s[i] == 'R':
        last_r = i
    else:
        if last_r != -1:
            ans = min(ans, (l[i] - l[last_r]) // 2)
if ans == 10 ** 18:
    print(-1)
else:
    print(ans)


n = int(input())
a = input()
answer = float('infinity')
A = list(map(int, input().split()))
for i in range(n-1):
    if a[i]=='R' and a[i+1] == 'L':
        answer = min(answer, (A[i+1] - A[i])//2)
if answer != float('infinity'):
    print(answer)
else:
    print(-1)

n = int(input())
s = input()
a = list(map(int, input().split()))
maxl = -1
mini = 100000000000000000000000
for i in range(n):
    if s[i] == 'R':
        maxl = a[i]
    if s[i] == 'L' and maxl != -1:
        mini = min(mini, a[i] - maxl)
if mini == 100000000000000000000000:
    print(-1)
else:
    print(mini // 2)


N = int(input())
directions = input()
points = [int(x) for x in input().split()]
answer = -1
for i in range(0, N-1):
	if directions[i]=='R' and directions[i+1]=='L':
		if answer==-1 or answer>(points[i+1]-points[i])//2:
			answer = (points[i+1]-points[i])//2
print (answer)

n = int(input())
s = input().rstrip()
a = list(map(int, input().split()))
l, r = [], []
for i in range(n):
    if s[i] == 'R':
        r.append(a[i])
    else:
        l.append(a[i])
i = j = 0
ans = 10 ** 10
while i < len(r) and j < len(l):
    if r[i] < l[j]:
        ans = min(ans, l[j] - r[i])
        i += 1
    else:
        j += 1
if ans == 10 ** 10:
    print(-1)
else:
    print(ans // 2)

input()
l=list(input())
x=list(map(int,input().split(' ')))

p = [ i for i in range(len(l)-1) if l[i]=='R' and l[i+1]=='L']

if not p :
    print(-1)
else :
    t = [x[i+1]-x[i] for i in p]
    print(min(t)//2)

n = int(input())
direction = input()
xi = [int(x) for x in input().split(' ')]

m = []

for i in range(n-1):
	if direction[i:i+2] != 'RL': continue
	m.append(xi[i+1] - xi[i])

if not m: print(-1)
else: print(int(min(m)/2))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time

n   = int(input())

N   = [i for i in input()]
x   = [int(i) for i in input().split()]

start = time.time()

flag = False
ans  = float('Inf')

for i in range(n):
    if N[i] == 'R':
        left = i
        flag = True
    elif flag == True:
         buf = x[i] - x[left]
         if buf < ans:
             ans = buf
         flag = False

if ans < float('Inf'):
    print(ans//2)
else:
    print(-1)

finish = time.time()
#print(finish - start)


n = int(input())
s = input()
ans = 1234567890
i = 0
last_r = -1
for x in input().split():
    now = int(x)
    if s[i] == 'R':
        
        last_r = now
    else:
        if last_r != -1:
            ans = min(ans,(now-last_r)//2)
            
    i+=1
if ans == 1234567890:
    print('-1')
else:
    print(ans)


n = int(input())
s = list(input())
x = list(map(int,input().split()))

ans = 10**10

for i in range(n-1):
    if s[i] == "R" and s[i+1] == "L":
        ans = min(ans, (x[i+1] - x[i]) // 2)

if ans > 10 ** 9:
    ans = -1

print(ans)


NONE = 10 ** 10

n = int(input())
direct = input()
pos = [int(x) for x in input().split()]

best = NONE
for i,x in enumerate(pos):
    if i+1 == n:
        break
    if direct[i:i+2] != 'RL':
        continue

    best = min(best, pos[i+1] - x)

if best == NONE:
    best = -1
else:
    best = best // 2

print(best)


n=int(input())
s=input()
x=list(map(int,input().split()))
p=sorted([(x[i],s[i]) for i in range(n)])
ans=-1
mi=10**10
for i in range(1,n):
    if p[i-1][1]=='R' and p[i][1]=='L' and p[i][0]-p[i-1][0]<mi:
        mi=p[i][0]-p[i-1][0]; ans=mi//2
print(ans)

n = int(input())
d = input()
x = list(map(int, input().split()))
inf = 10**10
def solve():
    if n == 1:
        return -1
    ret = inf
    for i in range(1, n):
        if d[i - 1] == 'R' and d[i] == 'L':
            ret = min(ret, (x[i] - x[i - 1]) // 2)
    if ret == inf:
        return -1
    return ret
print(solve())            


#!/usr/bin/env python3

try:
    while True:
        n = int(input())
        s = input()
        a = list(map(int, input().split()))
        result = -1
        for i in range(1, n):
            if s[i - 1] == 'R' != s[i]:
                t = (a[i] - a[i - 1]) >> 1
                if result == -1 or t < result:
                    result = t
        print(result)

except EOFError:
    pass


input()
ds = str.strip(input())
xs = list(map(int, str.split(input())))


best = None
last_right = None
for d, x in zip(ds, xs):

    if d == "R":

        last_right = x

    elif last_right is not None:

        t = (x - last_right) // 2
        best = min(best or t, t)

print(best or -1)


n = int(input())
st = input()
a = [int(i) for i in input().split()]

for i in range(n-1):
	if(a[i]==a[i+1]):
		print(0)
		return

ans = 10**9
for i in range(n-1):
	if st[i]=='R' and st[i+1]=='L': ans = min(ans,(a[i+1]-a[i])//2)

if ans!=10**9: print(ans)
else: print(-1)

n = int(input())
velocities = input()
coordinates = input()
speed = [0] * n
time = 10**9

coordinates = list(map(int, coordinates.split()))

for i in range(len(velocities) - 1):
    if velocities[i] == 'R' and velocities[i + 1] == 'L':
        time = min(time, (coordinates[i + 1] - coordinates[i]) // 2)

if time == 10**9:
    time = -1
print(time)

n=int(input())
s=str(input())
ip=list(map(int,input().split()))
q=[1 for i in range(n)]
op=[]
for i in range(n):
    if s[i]=='L':
        q[i]=-q[i]
for i in range(n-1):
    if q[i+1]-q[i]<0:
        op.append((ip[i+1]-ip[i])/abs(q[i+1]-q[i]))
if len(op)==0:
    print(-1)
else:
    print(int(min(op)))


def main():
    input()
    l, r = [], []
    for c, x in zip(input(), list(map(int, input().split()))):
        if c == 'L':
            l.append(x)
        else:
            r.append(x)
    ilo, ihi = iter(r), iter(l)
    res = 10 ** 10
    try:
        lo, hi = next(ilo), next(ihi)
        while True:
            if lo < hi:
                if res > hi - lo:
                    res = hi - lo
                lo = next(ilo)
            else:
                hi = next(ihi)
    except StopIteration:
        print(res // 2 if res < 10 ** 10 else -1)


def __starting_point():
    main()

__starting_point()

def main():
    n = input()
    s = input()
    d = input()
    number = []
    res = False
    maxi = float('inf')
    for i in d.split(" "):
        number.append(int(i))
    for i in range(len(s) - 1):
        if ( s[i] == "R" and s[i + 1] == "L" ):
            cal = number[i+1] - number[i]
            if (cal < maxi):
                maxi = cal
            res = True
    
    if (res == True):
        maxi = int(maxi/2)
        print(maxi)
    else:
        print("-1")

main()


3

inf = 1e9

def main():
    n = int(input())
    dir = input()
    coords = list(map(int, input().split()))

    res = inf
    maxr = -1
    for i in range(n):
        if dir[i] == "R":
            maxr = coords[i]
        else:
            if maxr != -1:
                res = min((coords[i] - maxr) / 2, res)

    if res == inf:
        print(-1)
    else:
        print(int(res))

main()


n = int(input())
s = input()
pos = [int(i) for i in input().split()]
min = 10**18
nosol = True
for i in range(1,n):
	if s[i-1] == 'R' and s[i] == 'L':
		dist = pos[i] - pos[i-1]
		if dist < min:
			min = dist
			nosol = False
if nosol:
	print(-1)
else:
	print(min>>1)