問題文

($1, 2, 3, \dots, N$) を並び替えた数列 $A$ と、長さ $N - 1$ の > と < からなる文字列 $S$ が与えられます。

あなたは、数列 $A$ に対し以下の操作を $0$ 回以上好きな回数行うことができます。

• 数列 $A = (A_1, A_2, A_3, \dots, A_{N - 1}, A_N)$ を $A' = (A_2, A_3, A_4, \dots, A_N, A_1)$ に置き替える。

操作を行った後、以下の条件を満たすことができるかを判定し、できるならば条件を満たすために必要な操作の最小回数を求めてください。

• 各 $i$ ($1 \leq i \leq N - 1$) について、$A_i < A_{i + 1}$ ならば $S_i =$ <、$A_i > A_{i + 1}$ ならば $S_i =$ >

制約

• $N$ は整数
• $2 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq N$ ($1 \leq i \leq N$)
• $A$ は ($1, 2, 3, \dots, N$) の並び替え
• $S$ は長さ $N - 1$ の > または < からなる文字列

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$S$

出力

何回操作しても条件を満たすことができないなら $-1$ を出力せよ。条件を満たすことができる場合は、条件を満たすために必要な操作の最小回数を出力せよ。

サンプル

3
1 2 3
><

2

5
1 2 3 4 5
<<<<

0

4
4 3 2 1
<<<

-1

9
1 7 6 8 9 2 3 5 4
<>><><<>

6