Longest Pattern Subsequence in a Permutation

Farmer John has N cows numbered 1 through N arranged in a permutation p₁, p₂, …, p_N. You are also given a string S of length N-1 consisting of the characters U and D. We say that a sequence a₀, a₁, …, a_K (where the indices of the cows in p are in increasing order) is pattern‐compatible if for every j from 1 to K the following holds:

• If the j^th character of S is U then a_j-1 < a_j.
• If the j^th character of S is D then a_j-1 > a_j.

Your task is to determine the maximum integer K (with K ≤ N-1) for which there exists a subsequence of p of length K+1 that is pattern‐compatible with the first K characters of S. In other words, if we denote by S the string \[ S = s_1 s_2 \cdots s_{N-1}, \] find the largest K (with 0 ≤ K ≤ N-1) for which there exists indices \[ i_0 < i_1 < \cdots < i_K \] such that for every j = 1, 2, \dots, K: \[ \text{if } s_j = \text{U} \text{ then } p_{i_{j-1}} p_{i_j}. \]

Note: If K = 0, the subsequence consists of a single element and is always valid.

inputFormat

The first line contains an integer N (2 ≤ N ≤ 3×10^5).

The second line contains N space‐separated integers representing the permutation p.

The third line contains a string S of length N-1 consisting of characters 'U' and 'D'.

outputFormat

Output a single integer: the maximum K (with K ≤ N-1) such that there exists a subsequence of p of length K+1 meeting the pattern described by the first K characters of S.

sample

4
4 1 3 2
UD

2