AT_arc141_c [ARC141C] Bracket and Permutation

[problemUrl]: https://atcoder.jp/contests/arc141/tasks/arc141_c 長さ $ 2N $ の文字列 $ S=S_1S_2\dots\ S_{2N} $ について、 $ S $ が $ N $ 個の `(` , および $ N $ 個の `)` で構成されるとき、 $ S $ は「括弧列」であるといいます。 また、「括弧列」$ S $ のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。 - 空文字列 - ある「正しい括弧列」$ A $ が存在して `(`, $ A $, `)` をこの順に連結した文字列 - ある空でない「正しい括弧列」$ A,\ B $ が存在して、 $ A,\ B $ をこの順に連結した文字列 $ 1 $ から $ 2N $ までの整数からなる $ 2 $ つの順列 $ P=(P_1,\ P_2,\ \dots,\ P_{2N}),\ Q=(Q_1,\ Q_2,\ \dots,\ Q_{2N}) $ が与えられます。 以下の条件を満たすような「括弧列」$ S=S_1S_2\dots\ S_{2N} $ が存在するか判定してください。 - $ S_{p_1}S_{p_2}\dots\ S_{p_{2N}} $ が「正しい括弧列」となるような $ 1 $ から $ 2N $ までの整数の順列 $ p $ のうち、辞書式順序で最小のものが $ P $ - $ S_{p_1}S_{p_2}\dots\ S_{p_{2N}} $ が「正しい括弧列」となるような $ 1 $ から $ 2N $ までの整数の順列 $ p $ のうち、辞書式順序で最大のものが $ Q $ 存在する場合は $ 1 $ つ求めてください。

N/A

N/A

### 制約 - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ P_i,Q_i\ \leq\ 2N $ - $ P,\ Q $ はそれぞれ $ 1 $ から $ 2N $ までの整数の順列 - 入力される値はすべて整数 ### Sample Explanation 1 $ S= $ `())(` のとき、$ S_{p_1}S_{p_2}S_{p_3}S_{p_4} $ が「正しい括弧列」となる $ p $ は $ p=(1,\ 4,\ 2,\ 3),\ (1,\ 4,\ 3,\ 2) $ などが考えられますが、このうち辞書式順序で最小のものは $ p=(1,\ 2,\ 4,\ 3) $ 、最大のものは $ p=(4,\ 3,\ 1,\ 2) $ であり、 $ S $ は条件を満たします。 ### Sample Explanation 2 条件を満たす $ S $ は存在しません。