G. The blut dot game
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The students from IME-USP are obsessed with games, a very popular game among the students is the blue dot game. In this game, $$$n$$$ students form a circle such that each student can see the other $$$n - 1$$$ students, and each student has a blue or brown dot painted on their forehead. The objective of the game is to find out which students have a blue dot on the forehead, but, initially, nobody knows the color painted on its own forehead. The game works with turns, when a student discovers the answer he leaves the circle at the end of the turn, the game ends when all students leave the circle.

In this version of the game, it is always guaranteed that at least one student has a blue dot on his forehead.

This time the students started the game just before class! The professors do not want to interrupt the game because it is an important tradition, however, they want to know how many turns the game is going to last. Keep in mind that the students from IME-USP are very smart and always finish the game as fast as possible.

Input

The first line contains one integer $$$n\ (1 \leq n \leq 2*10^5)$$$, the number of students.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n\ (a_i \in \{0, 1\})$$$ such that if $$$a_i = 0$$$ then the student has a brown dot and $$$a_i = 1$$$ if the student has a blue dot. It is guaranteed that at least one student has a blue dot.

Output

A single integer, the number of turns the game is going to last.

Examples
Input
1
1
Output
1
Input
2
0 1
Output
2