One More Merge - Repovive Starter Round 9 | Repovive

25B. One More Merge

1000 pts1s256 MB

You are given an array $a$ of $n$ positive integers.

In one operation, choose two adjacent elements $x$ and $y$ and replace them with the single number $\min(x,y)+1$ . The other elements keep their relative order.

Find the minimum possible value of the remaining element after $n-1$ operations.

Constraints

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

Output

\mathrm{answer}

Samples

Input

3
1 8 8

Explanation

Merge the two elements equal to $8$ , obtaining $[1,9]$ . Merge the remaining pair to obtain $2$ . Since every merge produces a number at least $2$ , this is optimal.

Output

Input

3
8 1 8

Explanation

The first operation produces either $[2,8]$ or $[8,2]$ . In both cases, the final operation produces $3$ .

Output

Input

4
8 1 1 8

Explanation

Merge the first two elements, obtaining $[2,1,8]$ . Merge the last two elements to obtain $[2,2]$ , and then merge once more to obtain $3$ . No order of operations produces a value smaller than $3$ .

Output

You are given an array $a$ of $n$ positive integers.

In one operation, choose two adjacent elements $x$ and $y$ and replace them with the single number $\min(x,y)+1$ . The other elements keep their relative order.

Find the minimum possible value of the remaining element after $n-1$ operations.

$2 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array}

\mathrm{answer}

Merge the two elements equal to $8$ , obtaining $[1,9]$ . Merge the remaining pair to obtain $2$ . Since every merge produces a number at least $2$ , this is optimal.

The first operation produces either $[2,8]$ or $[8,2]$ . In both cases, the final operation produces $3$ .

Merge the first two elements, obtaining $[2,1,8]$ . Merge the last two elements to obtain $[2,2]$ , and then merge once more to obtain $3$ . No order of operations produces a value smaller than $3$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

25B. One More Merge

Constraints

Input

Output

Samples

25B. One More Merge

Constraints

Input

Output

Samples