{"problem":{"name":"Too Heavy","description":{"content":"There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Bagg","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc111_c"},"statements":[{"statement_type":"Markdown","content":"There are $N$ people numbered $1$ to $N$ and $N$ pieces of baggage numbered numbered $1$ to $N$. Person $i$ has a weight of $a_i$, and Baggage $j$ has a weight of $b_j$. Initially, Person $i$ has Baggage $p_i$. We want to do the operation below zero or more times so that each Person $i$ will have Baggage $i$.\n\n*   Choose $i,j (i \\neq j)$, and swap the baggages of Person $i$ and Person $j$.\n\nHowever, when a person has a piece of baggage with a weight **greater than or equal to** his/her own weight, the person gets tired and becomes unable to take part in a future operation (that is, we cannot choose him/her as Person $i$ or $j$). Particularly, if $a_i \\leq b_{p_i}$, Person $i$ cannot take part in any operation.\nDetermine whether there is a sequence of operations that achieves the objective, and if so, construct one such sequence **with the minimum possible number of operations**.\n\n## Constraints\n\n*   $1 \\leq N \\leq 200000$\n*   $1 \\leq a_i,b_i \\leq 10^9$\n*   $p$ is a permutation of $1, \\ldots, N$.\n*   All numbers in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $\\ldots$ $a_N$\n$b_1$ $b_2$ $\\ldots$ $b_N$\n$p_1$ $p_2$ $\\ldots$ $p_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc111_c","tags":[],"sample_group":[["4\n3 4 8 6\n5 3 1 3\n3 4 2 1","3\n3 4\n1 3\n4 2\n\nInitially, People $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 3, 5$, respectively, so no one is tired.\nFirst, we do the operation choosing Person $3$ and $4$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $1, 3, 5, 3$, so no one is tired yet.\nSecond, we do the operation choosing Person $1$ and $3$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so Person $1$ gets tired.\nLastly, we do the operation choosing Person $4$ and $2$. Now, people $1, 2, 3, 4$ has pieces of baggage with weights $5, 3, 1, 3$, so no one gets tired.\nThis sequence of operations has made everyone have the right piece of baggage, with the minimum possible number of operations, so it is valid."],["4\n1 2 3 4\n4 3 2 1\n4 3 2 1","\\-1\n\nNo sequence of operations achieves the objective."],["1\n58\n998244353\n1","0\n\nThe objective is already achieved in the initial state."]],"created_at":"2026-03-03 11:01:14"}}