무한 알람

해외여행의 마지막 저녁이고, 내일 비행기를 타기 위해 일찍 일어나야 한다. 하지만 휴대전화가 고장 났고 방에는 다른 알람 시계도 없다는 사실을 알게 된다. 스스로 잠에서 깨어날 수 있는 유일한 방법은 적절한 순간에 컴퓨터를 과열시켜 큰 소리가 나게 하는 것이다. 이를 위해 여러 단계를 거친 뒤 무한히 큰 수의 집합을 만들어 내는 복잡한 알고리즘을 구현하기로 한다.

$S$인 $N$개의 양의 정수로 이루어진 집합이 주어진다. $x$보다 엄격히 작은 $S$의 원소 수가 홀수인 양의 정수 $x$의 집합을 $f(S)$라고 하자.

매초 집합 $S$은 $f(S)$로 대체된다. 집합 $S$의 크기가 무한해질 때까지 몇 초가 걸리는지 계산하는 것이 과제다.

채점

여러 테스트 그룹으로 해답을 평가하며, 각 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스를 포함한다. 테스트 그룹의 점수를 얻으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제약 조건

$1$ |$15$| $N \leq 2$

$2$ |$30$| $N \leq 100$, $s_i \leq 3 \cdot 10^5$

$3$ |$55$| 추가 제약 조건 없음.

첫째 줄에 정수 하나 $N$ ($1 \leq N \leq 5 \cdot 10^5$)가 주어진다.

둘째 줄에 집합 $S$의 정수인 $N$개의 정수 $s_1, s_2, \dots, s_N$ ($1 \leq s_i \leq 10^9$)가 주어진다. 이 정수들은 모두 서로 다르다.

집합 $S$의 원소가 무한히 많아질 때까지 걸리는 초 수를 정수로 출력한다.