很快就会推出一个新的、强大的、不寻常的对撞机,它位于一条直线上。 n 个粒子将被发射到其中。它们全部位于一条直线上,并且不能有两个或多个粒子位于同一点。粒子的坐标与距碰撞器中心的距离(以米为单位)一致,xi 是第 i 个粒子的坐标及其同时在碰撞器中的位置。所有粒子位置的坐标都是偶数。
您知道每个粒子运动的方向 - 在对撞机发射开始后它将向右或向左移动。在对撞机发射开始时,所有粒子开始同时移动。每个粒子都会以每微秒 1 米的恒定速度向左或向右直线运动。对撞机足够大,因此粒子无法在可预见的时间内离开它。
编写程序,找出对撞机任意两个粒子第一次碰撞的时刻。换句话说,找到任意两个粒子位于同一点的第一时刻之前的微秒数。
输入
第一行包含正整数 n (1 ≤ n ≤ 200 000) — 粒子数。
第二行包含n个符号“L”和“R”。如果第 i 个符号等于“L”,则第 i 个粒子将向左移动,否则第 i 个符号等于“R”,第 i 个粒子将向右移动。
第三行包含成对不同偶数 x1, x2, ..., xn (0 ≤ xi ≤ 109) 的序列——按从左到右的顺序排列的粒子坐标。保证粒子的坐标按升序给出。
输出
在第一行中打印唯一的整数——两个粒子位于同一点并且发生爆炸的第一个时刻(以微秒为单位)。
如果粒子碰撞没有发生,则打印唯一的整数-1。
示例
输入 #1
4 RLRL 2 4 6 10
输出 #1
1
输入 #2
3 LLR 40 50 60
输出 #2
-1
注意
在第一个示例中,第一次爆炸将在 1 微秒内发生,因为编号 1 和 2 的粒子将同时位于坐标为 3 的同一点。
在第二个示例案例中,不会发生爆炸,因为没有粒子同时位于同一点。