Page not loading? Try clicking here.
Placeholder

#7017
Subtask

두 배 2s 1024MB

Problems

길이 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)


Input

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

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


Output

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


Subtask

# Score Condition
#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

추가 제약 조건 없음


Example #1

5
3 1 4 1 5
4

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


Example #2

5
3 1 5 1 5
6

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


Example #3

5
1 2 3 4 5
0


Source

KOI 1차 2024 초2/중1

You must sign in to write code.