← 返回题目列表

AtCoder · asaporo_b

B. 压缩

中文机器翻译题面 查看原题

分数: 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 是 M or m.

部分分数

  • 在测试集中值得 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