Problem Statement

There is an undirected graph $G$ with $N$ vertices and $N$ edges.

The edges of $G$ are given by a permutation $P$ of $(1,2,\dots,N)$. For $1 \le i \le N$, the $i$-th edge connects vertex $P_i$ and vertex $P_{i+1}$. Here, vertex $P_{N+1}$ refers to vertex $P_1$.

Initially, all vertices of the graph $G$ are painted white.

You may perform the following sequence of operations any number of times, $0$ or more.

1. Choose $0$ or more edges of the graph $G$ and remove them.
2. For each connected component of the graph $G$, perform the following process.
   • Paint black the vertex with the largest vertex number in the connected component. If that vertex is already painted black, do nothing.
3. Restore the removed edges of the graph $G$.

You are given a string $S$ of length $N$ consisting of B and W. You want vertex $i$ to be painted black if the $i$-th character of $S$ is B, and vertex $i$ to be painted white otherwise.

Determine whether this can be achieved by performing the operations, and if it is possible, find the minimum number of operations required.

Input

$N$
$P_1\ P_2\ \dots \ P_N$
$S$

• $2 \le N \le 3 \times 10^5$
• $P$ is a permutation of $(1,2,\dots,N)$.
• $S$ is a string of length $N$ consisting of B and W.

Output

If the goal can be achieved, print the minimum number of operations; otherwise, print -1. Print a newline at the end.

Sample

4
2 4 1 3
BBWB

2

4
2 4 1 3
BBBB

1

4
2 4 1 3
BBBW

-1