{"problem":{"name":"Bracket and Permutation","description":{"content":"A string of length $2N$, $S=S_1S_2\\dots S_{2N}$, is said to be a _parenthesis sequence_ when $S$ is composed of $N$ `(`s and $N$ `)`s. Additionally, a parenthesis sequence $S$ is said to be _correct_ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc141_c"},"statements":[{"statement_type":"Markdown","content":"A string of length $2N$, $S=S_1S_2\\dots S_{2N}$, is said to be a _parenthesis sequence_ when $S$ is composed of $N$ `(`s and $N$ `)`s.\nAdditionally, a parenthesis sequence $S$ is said to be _correct_ when it is one of the following.\n\n*   An empty string.\n*   The concatenation of `(`, $A$, `)` in this order, where $A$ is a correct parenthesis sequence.\n*   The concatenation of $A$, $B$ in this order, where $A$ and $B$ are non-empty correct parenthesis sequences.\n\nYou are given two permutations $P=(P_1,\\ P_2,\\ \\dots,\\ P_{2N})$ and $Q=(Q_1,\\ Q_2,\\ \\dots,\\ Q_{2N})$ of the integers from $1$ to $2N$.\nDetermine whether there exists a parenthesis sequence $S=S_1S_2\\dots S_{2N}$ that satisfies the following conditions.\n\n*   $P$ is the lexicographically smallest permutation $p$ of the integers from $1$ to $2N$ such that $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ is a correct parenthesis sequence.\n*   $Q$ is the lexicographically largest permutation $p$ of the integers from $1$ to $2N$ such that $S_{p_1}S_{p_2}\\dots S_{p_{2N}}$ is a correct parenthesis sequence.\n\nIf such a parenthesis sequence exists, find one.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq P_i,Q_i \\leq 2N$\n*   Each of $P$ and $Q$ is a permutation of $1$ to $2N$.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_{2N}$\n$Q_1$ $Q_2$ $\\dots$ $Q_{2N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc141_c","tags":[],"sample_group":[["2\n1 2 4 3\n4 3 1 2","())(\n\nFor $S=$ `())(`, some of the permutations $p$ such that $S_{p_1}S_{p_2}S_{p_3}S_{p_4}$ is a correct parenthesis sequence are $p=(1,\\ 4,\\ 2,\\ 3),\\ (1,\\ 4,\\ 3,\\ 2)$. The lexicographically smallest and largest among them are $p=(1,\\ 2,\\ 4,\\ 3)$ and $p=(4,\\ 3,\\ 1,\\ 2)$, satisfying the conditions."],["2\n1 3 2 4\n4 3 2 1","\\-1\n\nNo $S$ satisfies the conditions."],["3\n2 1 5 3 4 6\n6 5 3 4 2 1","\\-1"]],"created_at":"2026-03-03 11:01:14"}}