問題一覧 > 通常問題

No.1859 ><<<

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 39
作問者 : ShirotsumeShirotsume / テスター : 👑 potato167potato167
5 ProblemId : 7375 / 自分の提出
問題文最終更新日: 2022-07-20 02:06:56

問題文

($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$ を出力せよ。条件を満たすことができる場合は、条件を満たすために必要な操作の最小回数を出力せよ。

最後に改行すること。

サンプル

サンプル1
入力
3
1 2 3
><
出力
2

$A$ に対し $2$ 回操作を行うと、数列は 3 1 2 となります。これは条件を満たします。

$1$ 回以下の操作で条件を満たすことはできないので、 $2$ を出力してください。

サンプル2
入力
5
1 2 3 4 5
<<<<
出力
0

操作をしなくても条件を満たしているときは、 $0$ を出力してください。

サンプル3
入力
4
4 3 2 1
<<<
出力
-1

何回操作を行っても条件を満たせないならば、 $-1$ を出力してください。

サンプル4
入力
9
1 7 6 8 9 2 3 5 4
<>><><<>
出力
6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。