分数: 1400 点
问题陈述
Takahashi 找到了一个整数序列 (A_1,A_2,...,A_N) 与 N 条款。由于它太重而无法携带,因此他决定将其压缩为单个整数。
压缩发生在 N-1 步骤,每个步骤都会将序列的长度缩短 1。让 S 是描述步骤以及执行顺序的字符串 i第步执行为 (a_1,a_2,...,a_K),那么 i第一步如下:
- 当 i- 第一个字符 S is
M,让 b_i = max(a_i,a_{i+1}) (1 ≦ i ≦ K-1),并将当前序列替换为 (b_1,b_2,...,b_{K-1}). - 当 i- 第一个字符 S is
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 是
Morm.
部分分数
- 在测试集中值得 400 点,存在 i (1 ≦ i < N-1) 这样第一个 i 中的字符 S 是
M,其余字符是m,即 S 的形式为M...Mm...m. - 在测试集中值得 800 点,第奇数个字符 S 是
M,偶数个字符是m,即 S 的形式为MmMmMm....
输入
输入由标准输入按以下格式给出:
N A_1 A_2 … A_N S
输出
打印从压缩中获得的单个整数。
示例输入 1
4 1 2 3 4 MmM
示例输出 1
3
初始序列 ( 1 , 2 , 3 , 4 ) 压缩如下:
- 第一步之后,顺序是 ( 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