QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[0]

# 3551. Up Down Subsequence

Statistics

Farmer John's N cows (2N3105), conveniently numbered 1N as usual, have ordered themselves according to a permutation p1,p2,,pN of 1N. You are also given a string of length N1 consisting of the letters U and D. Please find the maximum KN1 such that there exists a subsequence a0,a1,,aK of p such that for all 1jK, aj1<aj if the jth letter in the string is U, and aj1>aj if the jth letter in the string is D.

Input Format

The first line contains N.

The second line contains p1,p2,,pN.

The last line contains the string.

Output Format

Write out maximum possible value of K.

Sample Input

5
1 5 3 4 2
UDUD

Sample Output

4

We can choose [a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5]; the entire permutation is consistent with the string.

Sample Input

5
1 5 3 4 2
UUDD

Sample Output

3

We can choose [a0,a1,a2,a3]=[p1,p3,p4,p5].

Scoring

  • Test cases 3-4 satisfy N500.
  • Test cases 5-8 satisfy N5000.
  • In test cases 9-12, the string consists of Us followed by Ds.
  • Test cases 13-22 satisfy no additional constraints.

Problem credits: Danny Mittal