{"problem":{"name":"Takahashi Quest","description":{"content":"Takahashi will embark on an adventure. During the adventure, $N$ events will occur. The $i$\\-th event $(1\\leq i\\leq N)$ is represented by a pair of integers $(t _ i,x _ i)$ $(1\\leq t _ i\\leq 2,1\\leq x","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc333_e"},"statements":[{"statement_type":"Markdown","content":"Takahashi will embark on an adventure.\nDuring the adventure, $N$ events will occur. The $i$\\-th event $(1\\leq i\\leq N)$ is represented by a pair of integers $(t _ i,x _ i)$ $(1\\leq t _ i\\leq 2,1\\leq x _ i\\leq N)$ and is as follows:\n\n*   If $t _ i=1$, he finds one potion of type $x _ i$. He can choose to pick it up or discard it.\n*   If $t _ i=2$, he encounters one monster of type $x _ i$. If he has a potion of type $x _ i$, he can use one to defeat the monster. If he does not defeat it, he will be defeated.\n\nDetermine whether he can defeat all the monsters without being defeated.\nIf he cannot defeat all the monsters, print `-1`.\nOtherwise, let $K$ be the maximum number of potions he has at some point during the adventure. Let $K _ {\\min}$ be the minimum value of $K$ across all strategies where he will not be defeated. Print the value of $K _ {\\min}$ and the actions of Takahashi that achieve $K _ {\\min}$.\n\n## Constraints\n\n*   $1\\leq N\\leq2\\times10^5$\n*   $1\\leq t _ i\\leq2\\ (1\\leq i\\leq N)$\n*   $1\\leq x _ i\\leq N\\ (1\\leq i\\leq N)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$t _ 1$ $x _ 1$\n$t _ 2$ $x _ 2$\n$\\vdots$\n$t _ N$ $x _ N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc333_e","tags":[],"sample_group":[["13\n1 2\n1 3\n1 1\n1 3\n1 2\n2 3\n1 3\n1 3\n2 3\n1 3\n2 2\n2 3\n2 1","3\n1 1 1 0 0 1 0 1\n\nThe sample output corresponds to the following actions:\n\n*   Find potions of types $2,3,1$ in this order. Pick up all of them.\n*   Find potions of types $3,2$ in this order. Do not pick up any of them.\n*   Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.\n*   Find a type-$3$ potion. Pick it up.\n*   Find a type-$3$ potion. Do not pick it up.\n*   Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.\n*   Find a type-$3$ potion. Pick it up.\n*   Encounter a type-$2$ monster. Use one type-$2$ potion to defeat it.\n*   Encounter a type-$3$ monster. Use one type-$3$ potion to defeat it.\n*   Encounter a type-$1$ monster. Use one type-$1$ potion to defeat it.\n\nIn this sequence of actions, the value of $K$ is $3$.\nThere is no way to avoid defeat with $K\\leq 2$, so the sought value of $K _ {\\min}$ is $3$. There are multiple sequences of actions that satisfy $K=3$ and allow him to avoid defeat; you may print any of them."],["4\n2 3\n1 4\n2 1\n1 2","\\-1\n\nHe will inevitably be defeated by the first monster he encounters."],["30\n1 25\n1 2\n1 10\n1 18\n2 18\n1 11\n2 11\n1 21\n1 6\n2 2\n2 10\n1 11\n1 24\n1 11\n1 3\n1 2\n1 18\n2 25\n1 8\n1 10\n1 11\n2 18\n2 10\n1 10\n2 2\n1 24\n1 10\n2 10\n1 25\n2 6","4\n1 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 0 0"]],"created_at":"2026-03-03 11:01:13"}}