Varză murată 是罗马尼亚酸菜，传统上是在含有盐和香料的盐水中发酵而成，因其浓郁的酸味而备受推崇，既可作为配菜，也是萨尔马莱（sarmale，一种罗马尼亚菜卷）等菜肴的关键原料。

今年将举办第 2025 届酸菜大赛（Murată Varză Contest, MVC）。比赛规则非常严格，但也非常奇特。一共有 $n$ 棵酸菜排成一排，其中第 $i$ 棵酸菜的酸度为 $a_i$。评委由两个人组成：Minnie 和 Maxim。

Minnie 喜欢不太酸的酸菜（这很奇怪），所以从她的角度来看，给定两棵酸菜 $i$ 和 $j$，酸度值较小的那棵获胜。Maxim 喜欢非常酸的酸菜，所以从他的角度来看，给定两棵酸菜 $i$ 和 $j$，酸度值较大的那棵获胜。因为他们无法达成一致，所以他们进行评判的顺序是由其他人决定的。

假设当前比赛中还剩下 $k$ 棵酸菜。如果轮到 Maxim 进行评判，他会遍历列表中每一对相邻的酸菜，并选择酸度较大的那一棵进入下一阶段。如果轮到 Minnie 进行评判，她会遍历列表中每一对相邻的酸菜，并选择酸度较小的那一棵进入下一阶段。得到的列表将恰好包含 $k - 1$ 棵酸菜。

请注意，列表中可能会多次包含同一棵酸菜。例如，如果列表中剩余酸菜的酸度为 $4, 8, 1$，那么 Minnie 评判后下一阶段的酸度列表将是 $4, 1$，而 Maxim 评判后的列表将是 $8, 8$（中间的那棵酸菜被晋级了两次）。

当 $k = 1$ 时，列表中剩下的一棵酸菜即为获胜者。非常心急的你希望尽快知道比赛结束时的获胜者。给定初始的酸度值以及两位评委的评判顺序，请计算最终获胜酸菜的酸度值。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示参赛的酸菜数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示酸度值（$1 \le a_i \le n$）。

第三行包含一个长度为 $n - 1$ 的字符串。每个字符要么是代表 Minnie 的 'm'，要么是代表 Maxim 的 'M'。

输出格式

输出一个整数，表示最终获胜酸菜的酸度值。

样例

输入样例 1

7
1 3 4 6 5 1 3
mMMmMm

输出样例 1

5

输入样例 2

7
4 5 3 6 5 1 3
mMMmMm

输出样例 2

5

输入样例 3

2
1 2
M

输出样例 3

2

说明

下图展示了第一个样例。最底层是初始的酸度值。往上每一层包含裁判进行一轮评判后的酸度值。