I. From Baikonur to Mars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Baikonur Cosmodrome, located in Kazakhstan, is the world's oldest space launch facility. Many historical flights lifted off from Baikonur: the first human-made satellite, Sputnik 1, in 1957; the first crewed spaceflight by Yuri Gagarin, in 1961; and the flight of the first woman in space, Valentina Tereshkova, in 1963. Today, one more historical rocket is lifting off, humanity is going to Mars!

You are an alien employee of the company Astronauts Coming to Mars (ACM) and want to make sure the rocket has enough space for a safe landing. Right now, the place where the humans will land is occupied by $$$n$$$ mountains, each with height $$$a_i$$$. You must destroy them all before the humans arrive.

You are allowed to do the following two operations:

  • Select a subset $$$S$$$ and decrease the height by one of every mountain in $$$S$$$;
  • Select a subset $$$S$$$ and change $$$a_i$$$ to $$$a_i \% 2$$$ (the remainder when $$$a_i$$$ is divided by 2) for every mountain in $$$S$$$.

What is the minimum number of operations to make all mountains have height zero?

Input

The first line has an integer $$$1 \leq n \leq 10^5$$$. The second line has $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$. It is guaranteed that at least one mountain has height strictly greater than zero.

Output

Output only one integer: the minimum number of operations to make all mountains have height zero.

Examples
Input
5
1 1 1 1 1
Output
1
Input
4
9 0 8 2
Output
2
Note

In the first case, you select all mountains and decrease their height by one. In the second case, you first use one operation to decrease the height of the first mountain and then use the remainder operation to destroy all mountains.