Up Down Subsequence

시간 제한2초메모리 제한1024 MB

요약

순열과 U/D 문자열이 주어질 때, 앞에서부터 K개의 부등호를 만족하는 부분수열의 최대 길이를 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 이분 탐색, 배열
정답자: 아직 제출이 없습니다

문제

Farmer John's $N$ cows ( $2 \leq N \leq 3\cdot 10^5$ ), conveniently numbered $1 \ldots N$ as usual, have ordered themselves according to a permutation $p\_1,p\_2,\ldots,p\_N$ of $1\ldots N$ . You are also given a string of length $N-1$ consisting of the letters U and D. Please find the maximum $K\le N-1$ such that there exists a subsequence $a\_0,a\_1,\ldots,a\_{K}$ of $p$ such that for all $1\le j\le K$ , $a\_{j - 1} < a\_j$ if the $j$ th letter in the string is U, and $a\_{j - 1} > a\_j$ if the $j$ th letter in the string is D.

입력

The first line contains $N$ .

The second line contains $p\_1,p\_2,\ldots,p\_N$ .

The last line contains the string.

출력

Write out maximum possible value of $K$ .

예제2

예제 1
입력
```
5
1 5 3 4 2
UDUD
```
예상 출력
```
4
```
예제 2
입력
```
5
1 5 3 4 2
UUDD
```
예상 출력
```
3
```