1, 2, ..., N의 수들이 순서가 섞인 형태의 길이 N의 순열 p₁, p₂, ..., p_n이 주어지고,

U, D의 문자로 구성된 길이 N-1의 문자열 S가 주어진다.

순열 p의 부분수열을 a₀, a₁, ..., a_k를 뽑아 1 <= j <= K인 모든 j에 대하여

S_j = 'U'일 때는 a_j-1 < a_j를, S_j = 'D'일 때는 a_j-1> a_j를 만족할 때 이 부분수열을 좋은 부분수열이라 한다.

가능한 모든 좋은 부분수열들 중 K의 최댓값을 구하여라.

[제약 조건]

2 <= N <= 3*10⁵

[Subtask]

Subtask #1 (10점) : N<=500

Subtask #2 (15점) : N<=5000

Subtask #3 (15점) : S는 UU...UDD...D의 형태이다. 즉 모든 U가 등장한 이후 모든 D가 등장한다.

Subtask #4 (60점) : 추가 제한 조건 없음

UD 순열 timer 2초 memory 1024MB

UD 순열 2초 1024MB