두 배

면접 대비

시간 제한1초메모리 제한1024 MB

요약

양의 정수 수열의 원소에 2를 곱하는 연산을 최소로 사용해 수열을 오름차순으로 만드는 횟수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 수학
정답자: 아직 제출이 없습니다

문제

길이 $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$ 를 오름차순으로 만들기 위해, 다음 연산을 몇 번이든 반복해서 적용할 수 있다.

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

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

입력

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

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

출력

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

제한

주어지는 모든 수는 정수이다.
$1 \le N \le 250\,000$
$1 \le A_i \le 1\,000\,000$ ( $1 \le i \le N$ )

예제3

예제 1
입력
```
5
3 1 4 1 5
```
예상 출력
```
4
```
예제 2
입력
```
5
3 1 5 1 5
```
예상 출력
```
6
```
예제 3
입력
```
5
1 2 3 4 5
```
예상 출력
```
0
```