페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#7017
서브태스크

두 배 2초 1024MB

문제

길이 N인 양의 정수열 A_1,\dots,A_N이 주어진다. 이 수열을 오름차순으로 만들려 한다.

수열 A_1,\dots,A_N이 오름차순이라는 것은, 각 i (1\le i \le N-1)에 대해 A_i \le A_{i+1}이라는 것이다.

수열 A를 오름차순으로 만들기 위해, 수열 A에 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

  • 어떤 i (1\le i \le N)에 대해 A_i에 2를 곱한다.

연산을 최소 횟수로 적용해서 A를 오름차순으로 만들고 싶다. 이때, 최소 횟수를 구하라.

[제약 조건]

주어지는 모든 수는 정수이다.

1 \le N \le 250,000

1 \le A_i \le 1,000,000 (1\le i \le N)


입력

첫 번째 줄에 N이 주어진다.

두 번째 줄에 A_1, \dots, A_N이 주어진다.


출력

첫 번째 줄에 답을 출력한다.


부분문제

번호 점수 조건
#112점

각 i(1\le i \le N)에 대해, A_i = 1 또는 A_i = 2

#210점

각 i(1\le i \le N)에 대해, A_i = 2^{k_i}를 만족하는 0 이상의 정수 k_i가 존재

#311점

N \le 10

#419점

각 i (1 \le i \le N)에 대해, A_i=2 또는 A_i=3

#520점

각 i (1 \le i \le N-1) 에 대해, A_i \ge A_{i+1}

#628점

추가 제약 조건 없음


예제1

입력
5
31415
출력
4

A_2, A_4에 각각 두 번씩 연산을 적용하면 된다. 연산을 적용한 이후에 수열 A는 [3,4,4,4,5]가 된다.


예제2

입력
5
31515
출력
6

A_2에 두 번, A_4에 세 번, A_5에 한 번 연산을 적용하면 된다. 연산을 적용한 이후에 수열 A는 [3,4,5,8,10]가 된다.


예제3

입력
5
12345
출력
0

태그

출처

KOI 1차 2024 초2/중1

역링크