問題一覧 > 通常問題

No.1859 ><<<

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : Shirotsume / テスター : 👑 potato167
お気に入りにしたユーザー ProblemId : 7375 / 自分の提出
問題文最終更新日: 2022-07-20 02:06:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given a sequence $A$ that is a permutation of ($1, 2, 3, \dots, N$), and a string $S$ of length $N - 1$ consisting of > and <.

You may perform the following operation on the sequence $A$ any number of times, possibly $0$ times.

  • Replace the sequence $A = (A_1, A_2, A_3, \dots, A_{N - 1}, A_N)$ with $A' = (A_2, A_3, A_4, \dots, A_N, A_1)$.

Determine whether the following condition can be satisfied after performing the operations, and if it can, find the minimum number of operations required to satisfy the condition.

  • For each $i$ ($1 \leq i \leq N - 1$), if $A_i < A_{i + 1}$ then $S_i =$ <, and if $A_i > A_{i + 1}$ then $S_i =$ >

Constraints

  • $N$ is an integer
  • $2 \leq N \leq 3 \times 10^5$
  • $1 \leq A_i \leq N$ ($1 \leq i \leq N$)
  • $A$ is a permutation of ($1, 2, 3, \dots, N$)
  • $S$ is a string of length $N - 1$ consisting of > or <

Input

The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ $\dots$ $A_N$
$S$

Output

If the condition cannot be satisfied no matter how many operations are performed, print $-1$. If the condition can be satisfied, print the minimum number of operations required to satisfy the condition.

Print a newline at the end.

Sample

Sample 1
Input
3
1 2 3
><
Output
2

After performing the operation $2$ times on $A$, the sequence becomes 3 1 2. This satisfies the condition.

The condition cannot be satisfied with $1$ or fewer operations, so print $2$.

Sample 2
Input
5
1 2 3 4 5
<<<<
Output
0

If the condition is already satisfied without performing any operations, print $0$.

Sample 3
Input
4
4 3 2 1
<<<
Output
-1

If the condition cannot be satisfied no matter how many operations are performed, print $-1$.

Sample 4
Input
9
1 7 6 8 9 2 3 5 4
<>><><<>
Output
6

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