$n$개의 양의 정수로 이루어진 수열 $a_1, a_2, ... , a_n$이 있다. 우리는 이 수열에 대해 아래의 연산을 자유롭게 시행할 수 있다.

• $1 ≤ l ≤ r ≤ n$인 $l, r$을 골라 $a_l, a_{l+1}, ... , a_{r-1}, a_r$을 $a_l$ $⊕$ $1, a_{l+1}$ $⊕$ $1, ... , a_{r-1}$ $⊕$ $1, a_r$ $⊕$ $1$로 바꾼다.

또한, 이 연산을 최소한으로 수행하여 주어진 수열을 다음을 만족하는 수열로 바꾸려고 한다.

• $a_1$ $\&$ $1, a_2$ $\&$ $1$$, ... ,$ $a_{n-1}$ $\&$ $1, a_n$ $\&$ $1$의 값이 전부 동일하다.

첫째 줄에 수열의 길이 $n$이 주어진다. $(1 ≤ n ≤ 200,000)$

둘째 줄에 $a_1, a_2, ... , a_n$이 공백으로 구분되어 주어진다. $(1 ≤ a_i ≤ 1,000)$