409753: GYM103729 G Brick

Apple Jack is an Earth pony who lives and works at Sweet Apple Acres and Pinkie Pie is an energetic Earth pony who loves party!!

One day, Pinkie Pie destroyed the wall around Sweet Apple Acres accidentally. To restore it rapidly by bricks, she summoned her friends for help.

With the endeavor of ponys, they simplified the problem in a formal way.

They considered the wall in ruins as an integer array $$$\{h_i\}$$$ of length $$$n$$$, and bricks of scale $$$1\times 2$$$ can be placed horizontally or vertically on it.

More specifically, one brick could:

1. Add $$$2$$$ to any $$$h_i$$$.

2. Add $$$1$$$ to both $$$h_i$$$ and $$$h_{i+1}$$$ if $$$h_i=h_{i+1}$$$.

We define that the wall is restored when there exists an integer $$$x$$$ satisfying $$$h_i=x$$$ for all $$$i$$$.

Now ponys want to know, what's the minimal possible height $$$x$$$ for a restored wall, or tell them it's impossible to restore the wall.

The first line contains an integers $$$n\ (1\le n\le 2\times 10^5)$$$ - the length of array $$$h$$$.

The second line contains $$$n$$$ integers $$$h_1,h_2,\dots,h_n\ (1\le h_i\le 10^9)$$$ - the elements of array $$$h$$$.

If the wall can't be restored, print a single integer: $$$-1$$$.

Otherwise, print an integer $$$x$$$ - the minimal height of the wall.

8
2 1 2 1 1 2 1 2

4

For the example we have a figure for explanation.