题目描述

高桥发现了一个有 $N$ 个项的整数序列 $(A_1,A_2,...,A_N)$。由于这个序列太长了以至于无法携带，他决定将其压缩成一个整数。

压缩过程需要 $N-1$ 步，每一步都会将序列的长度减少 $1$。设 $S$ 是描述每一步操作的字符串，第 $i$ 个步骤作用在序列 $(a_1,a_2,...,a_K)$ 上，那么第 $i$ 个步骤如下：

• 当 $S$ 的第 $i$ 个字符是 M 时，令 $b_i = \max(a_i,a_{i+1})$ $(1 ≤ i ≤ K-1)$，并将当前序列替换为 $(b_1,b_2,...,b_{K-1})$。
• 当 $S$ 的第 $i$ 个字符是 m 时，令 $b_i = \min(a_i,a_{i+1})$ $(1 ≤ i ≤ K-1)$，并将当前序列替换为 $(b_1,b_2,...,b_{K-1})$。

高桥决定了操作步骤 $S$，但是他太累了以至于无法进行压缩。代替高桥，找出压缩后得到的整数。

约束条件

• $2 ≤ N ≤ 10^5$
• $1 ≤ A_i ≤ N$
• $S$ 包含 $N-1$ 个字符。
• $S$ 中的每个字符要么是 M，要么是 m。

部分分数

• 在价值为 $400$ 分的测试集中，存在 $i (1 ≤ i < N-1)$，使得 $S$ 的前 $i$ 个字符都是 M，余下的字符都是 m，即 $S$ 的形式是 M...Mm...m。
• 在价值为 $800$ 分的测试集中，$S$ 的奇数位置上的字符是 M，$S$ 的偶数位置上的字符是 m，即 $S$ 的形式是 MmMmMm...。

---

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ … $A_N$ $S$

输出

输出压缩后得到的整数。

---

示例输入 1

4
1 2 3 4
MmM

示例输出 1

3

初始序列 $( 1 , 2 , 3 , 4 )$ 经过以下压缩过程得到整数 $3$：

• 第一步后，序列变为 $( 2 , 3 , 4 )$。
• 第二步后，序列变为 $( 2 , 3 )$。
• 第三步后，序列变为 $( 3 )$。

因此，压缩后得到的整数是 $3$。

---

示例输入 2

5
3 4 2 2 1
MMmm

示例输出 2

2

---

示例输入 3

10
1 8 7 6 8 5 2 2 6 1
MmmmmMMMm

示例输出 3

5

---

示例输入 4

20
12 7 16 8 7 19 8 19 20 11 7 13 20 3 4 11 19 11 15 5
mMMmmmMMMMMMmMmmmMM

示例输出 4

11