No.1859 ><<<
タグ : / 解いたユーザー数 44
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。