题目描述

高橋君は $N$ 項からなる数列 $(A_1,A_2,...,A_N)$ を拾いました。数列を全部持ち帰るのは大変なので、高橋君は圧縮して一つの数にすることに決めました。

圧縮は $N-1$ 回のステップからなり、各ステップごとに今ある数列を、長さが $1$ 短い数列に圧縮します。ステップでの操作を表す文字列を $S$ として、今ある数列を $(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$ を決めましたが、疲れていて実際に圧縮することができません。代わりに、圧縮して得られる数を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $...$ $A_N$ $S$

输出格式

圧縮して高橋君が得られる数を出力せよ。

题目大意

极简翻译

一串数组a（a1,a2...aN）,一个由'M'和'm'组成的字符串S,并以S为指令对a进行压缩

对a数组进行以下操作（基于S的各个位置）:

1. 当S中的第i个字符为M时，令bi = max（ai，ai + 1）（1≤i≤K-1），并用（b1，b2，...，bK-1）替换当前序列。
2. 当S中的第i个字符为m时，令bi = min（ai，ai + 1）（1≤i≤K-1），并用（b1，b2，…，bK-1）替换当前序列。

k是当前b串的大小

请给出最终剩下的数字。

4
1 2 3 4
MmM

3

5
3 4 2 2 1
MMmm

2

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

5

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

11

提示

制約

• $2\ ≦\ N\ ≦\ 10^5$
• $1\ ≦\ A_i\ ≦\ N$
• $S$ は $N-1$ 文字からなり、各文字は M または m である。

部分点

• $400$ 点分のデータセットでは、ある $i\ (1\ ≦\ i\ <\ N-1)$ が存在して、$S$ の最初の $i$ 文字が M、その他の文字が m である。すなわち、$S$ は M...Mm...m のようになる。
• $800$ 点分のデータセットでは、$S$ の奇数文字目は M 、偶数文字目は m である。すなわち、$S$ は MmMmMm... のようになる。

Sample Explanation 1

最初の数列が $(\ 1\ ,\ 2\ ,\ 3\ ,\ 4\ )$ なので、 - $1$ 回目のステップでは数列 $(\ 2\ ,\ 3\ ,\ 4)$ に圧縮されます。 - $2$ 回目のステップでは数列 $(\ 2\ ,\ 3\ )$ に圧縮されます。 - $3$ 回目のステップでは数列 $(\ 3\ )$ に圧縮されます。 よって、求める数は $3$ です。