문제
1, 2, ..., N의 수들이 순서가 섞인 형태의 길이 N의 순열 p1, p2, ..., pn이 주어지고,
U, D의 문자로 구성된 길이 N-1의 문자열 S가 주어진다.
순열 p의 부분수열을 a0, a1, ..., ak를 뽑아 1 <= j <= K인 모든 j에 대하여
Sj = 'U'일 때는 aj-1 < aj를, Sj = 'D'일 때는 aj-1> aj를 만족할 때 이 부분수열을 좋은 부분수열이라 한다.
가능한 모든 좋은 부분수열들 중 K의 최댓값을 구하여라.
[제약 조건]
2 <= N <= 3*105
[Subtask]
Subtask #1 (10점) : N<=500
Subtask #2 (15점) : N<=5000
Subtask #3 (15점) : S는 UU...UDD...D의 형태이다. 즉 모든 U가 등장한 이후 모든 D가 등장한다.
Subtask #4 (60점) : 추가 제한 조건 없음
입력
다음과 같은 형식으로 입력이 주어진다.
N
p_1 p_2 ... p_N
S
출력
첫 줄에 정답을 출력한다.
예제1
입력
5
1 5 3 4 2
UDUD
출력
4
예제2
입력
5
1 5 3 4 2
UUDD
출력
3
출처
USACO 2022 US Open Platinum