Problem Description

Takahashi found a sequence of $ N $ numbers $ (A_1, A_2, ..., A_N) $. Carrying the entire sequence back is cumbersome, so Takahashi decided to compress it into a single number.

The compression consists of $ N-1 $ steps, each step reducing the current sequence by one element. Let $ S $ be the string representing the operations for each step, and let the current sequence be $ (a_1, a_2, ..., a_K) $. In the $ i $th step, the following operation is performed:

• If the $ i $th character of $ S $ is M, then $ b_i = max(a_i, a_{i+1}) $ $ (1 ≦ i ≦ K-1) $, and the sequence is compressed to $ (b_1, b_2, ..., b_{K-1}) $.
• If the $ i $th character of $ S $ is m, then $ b_i = min(a_i, a_{i+1}) $ $ (1 ≦ i ≦ K-1) $, and the sequence is compressed to $ (b_1, b_2, ..., b_{K-1}) $.

Takahashi has decided on the string $ S $ representing the steps for compression but is too tired to actually perform the compression. Instead, please determine the number obtained after compression.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the number that Takahashi would obtain after compression.

Sample Input and Output

Sample Input #1

4
1 2 3 4
MmM

Sample Output #1

3

Sample Input #2

5
3 4 2 2 1
MMmm

Sample Output #2

2

Sample Input #3

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

Sample Output #3

5

Sample Input #4

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

Sample Output #4

11

Notes/Hints

Constraints

• $ 2 ≦ N ≦ 10^5 $
• $ 1 ≦ A_i ≦ N $
• $ S $ consists of $ N-1 $ characters, each being either M or m.

Partial Points

• For $ 400 $ points, there exists an $ i $ $ (1 ≦ i < N-1) $ such that the first $ i $ characters of $ S $ are M and the rest are m. That is, $ S $ is of the form M...Mm...m.
• For $ 800 $ points, the odd-indexed characters of $ S $ are M and the even-indexed characters are m. That is, $ S $ is of the form MmMmMm....

Sample Explanation 1

The initial sequence is $ (1, 2, 3, 4) $, so:
- After the 1st step, the sequence is compressed to $ (2, 3, 4) $.
- After the 2nd step, the sequence is compressed to $ (2, 3) $.
- After the 3rd step, the sequence is compressed to $ (3) $.
Thus, the number to be found is $ 3 $.

见题面 Input 部分

见题面 Output 部分