Huawei prepares to blow up the market with its new super fast mobile device that is too secret to be named here. In order to make something really fast and reliable one needs to pay a lot of attention to details. You are working on a task that will affect how device picks a frequency for data transmission.

There are $$$n + 1$$$ different frequencies your new device is able to use. They are numbered from $$$0$$$ to $$$n$$$ with frequency $$$0$$$ being the most suitable for fast communication, frequency $$$1$$$ being the most suitable after $$$0$$$ and so on, $$$n$$$ is the least suitable frequency on the list. Unfortunately, you can't always use frequency $$$0$$$. For each of the next $$$n$$$ seconds there is exactly one frequency that will be banned for use because of maintenance. Indices of these frequencies are provided by a sequence of integers $$$a_1, a_2, \ldots, a_n$$$, each of them is from $$$0$$$ to $$$n$$$ inclusive.

Your goal is to split these $$$n$$$ seconds into $$$k$$$ periods, with each period being a non-empty sequence of consecutive seconds, such that each second belongs to exactly one period. Formally, you select integer lengths $$$l_1, l_2, \ldots, l_k$$$, such that $$$\sum_{i = 1}^{k} l_i = n$$$. Then, during the first period there will be a maintenance held at frequencies, $$$a_1, a_2, \ldots, a_{l_1}$$$, during the second period there will be a maintenance held at frequencies $$$a_{l_1+1}, a_{l_1+2}, \ldots, a_{l_1+l_2}$$$ and so on.

After you fix a split of $$$n$$$ seconds into periods, the device will automatically select a frequency for each period as the minimum frequency $$$x$$$ that will be available at any second of this period, i.e. minimum integer $$$x \geq 0$$$, such that $$$x \ne a_i$$$ for any $$$i$$$ of this period. Denote the frequencies being selected for these $$$k$$$ periods as $$$f_1, f_2, \ldots, f_k$$$. Note that these frequencies are selected automatically and the only way you can affect this process is by changing the way periods are chosen.

To care about users safety you will pick one emergency frequency $$$y$$$ for all periods. As an emergency frequency it won't be affected by any maintenance, so $$$y$$$ can be equal to any $$$a_i$$$, but it can't match any of $$$f_i$$$. One can show there will be always at least one valid $$$y$$$ available. Of course, you will pick minimum such $$$y$$$ as an emergency frequency.

The goal of this problem is to split $$$n$$$ seconds into $$$k$$$ periods in such a way that emergency frequency is minimum possible.