#P1188D. Make Equal
-
ID: 4847
Type: RemoteJudge
4000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Make Equal
No submission language available for this problem.
Description
You are given $n$ numbers $a_1, a_2, \dots, a_n$. In one operation we can add to any one of those numbers a nonnegative integer power of $2$.
What is the smallest number of operations we need to perform to make all $n$ numbers equal? It can be proved that under given constraints it doesn't exceed $10^{18}$.
The first line contains a single integer $n$ ($1 \le n \le 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^{17}$).
Output exactly one integer — the smallest number of operations we need to perform to make all $n$ numbers equal.
Input
The first line contains a single integer $n$ ($1 \le n \le 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^{17}$).
Output
Output exactly one integer — the smallest number of operations we need to perform to make all $n$ numbers equal.
Samples
4
228 228 228 228
0
3
2 2 8
3
Note
In the first example, all numbers are already equal. So the needed number of operation is $0$.
In the second example, we can apply the operation $3$ times: add $8$ to first $2$, add $8$ to second $2$, add $2$ to $8$, making all numbers equal to $10$. It can be proved that we can't make all numbers equal in less than $3$ operations.