{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003ca href\u003d\"https://codeforces.com/problemset/problem/1054/B\"\u003eProblem Link\u003c/a\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003cp\u003eInitially Ildar has an empty array. He performs $$$n$$$ steps. On each step he takes a subset of integers already added to the array and appends the \u003cspan class\u003d\"tex-font-style-tt\"\u003emex\u003c/span\u003e of this subset to the array. \u003c/p\u003e\u003cp\u003eThe \u003cspan class\u003d\"tex-font-style-tt\"\u003emex\u003c/span\u003e of an multiset of integers is the smallest \u003cspan class\u003d\"tex-font-style-bf\"\u003enon-negative\u003c/span\u003e integer not presented in the multiset. For example, the \u003cspan class\u003d\"tex-font-style-tt\"\u003emex\u003c/span\u003e of the multiset $$$[0, 2, 3]$$$ is $$$1$$$, while the \u003cspan class\u003d\"tex-font-style-tt\"\u003emex\u003c/span\u003e of the multiset $$$[1, 2, 1]$$$ is $$$0$$$.\u003c/p\u003e\u003cp\u003eMore formally, on the step $$$m$$$, when Ildar already has an array $$$a_1, a_2, \\ldots, a_{m-1}$$$, he chooses some subset of indices $$$1 \\leq i_1 \u0026lt; i_2 \u0026lt; \\ldots \u0026lt; i_k \u0026lt; m$$$ (possibly, empty), where $$$0 \\leq k \u0026lt; m$$$, and appends the $$$mex(a_{i_1}, a_{i_2}, \\ldots a_{i_k})$$$ to the end of the array.\u003c/p\u003e\u003cp\u003eAfter performing all the steps Ildar thinks that he might have made a mistake somewhere. He asks you to determine for a given array $$$a_1, a_2, \\ldots, a_n$$$ the minimum step $$$t$$$ such that he has definitely made a mistake on at least one of the steps $$$1, 2, \\ldots, t$$$, or determine that he could have obtained this array without mistakes.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ ($$$1 \\leq n \\leq 100\\,000$$$)\u0026nbsp;— the number of steps Ildar made.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$0 \\leq a_i \\leq 10^9$$$)\u0026nbsp;— the array Ildar obtained.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf Ildar could have chosen the subsets on each step in such a way that the resulting array is $$$a_1, a_2, \\ldots, a_n$$$, print $$$-1$$$.\u003c/p\u003e\u003cp\u003eOtherwise print a single integer $$$t$$$\u0026nbsp;— the smallest index of a step such that a mistake was made on at least one step among steps $$$1, 2, \\ldots, t$$$.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 1 2 239\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example it is possible that Ildar made no mistakes. Here is the process he could have followed.\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1$$$-st step. The initial array is empty. He can choose an empty subset and obtain $$$0$$$, because the \u003cspan class\u003d\"tex-font-style-tt\"\u003emex\u003c/span\u003e of an empty set is $$$0$$$. Appending this value to the end he gets the array $$$[0]$$$. \u003c/li\u003e\u003cli\u003e $$$2$$$-nd step. The current array is $$$[0]$$$. He can choose a subset $$$[0]$$$ and obtain an integer $$$1$$$, because $$$mex(0) \u003d 1$$$. Appending this value to the end he gets the array $$$[0,1]$$$. \u003c/li\u003e\u003cli\u003e $$$3$$$-rd step. The current array is $$$[0,1]$$$. He can choose a subset $$$[0,1]$$$ and obtain an integer $$$2$$$, because $$$mex(0,1) \u003d 2$$$. Appending this value to the end he gets the array $$$[0,1,2]$$$. \u003c/li\u003e\u003cli\u003e $$$4$$$-th step. The current array is $$$[0,1,2]$$$. He can choose a subset $$$[0]$$$ and obtain an integer $$$1$$$, because $$$mex(0) \u003d 1$$$. Appending this value to the end he gets the array $$$[0,1,2,1]$$$. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThus, he can get the array without mistakes, so the answer is $$$-1$$$.\u003c/p\u003e\u003cp\u003eIn the second example he has definitely made a mistake on the very first step, because he could not have obtained anything different from $$$0$$$.\u003c/p\u003e\u003cp\u003eIn the third example he could have obtained $$$[0, 1, 2]$$$ without mistakes, but $$$239$$$ is definitely wrong.\u003c/p\u003e"}}]}