J - Weird Sanchola Gym - 102302J

60 阅读 0 评论 40 点赞

我是靠谱客的博主缥缈哑铃，最近开发中收集的这篇文章主要介绍J - Weird Sanchola Gym - 102302J，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Sanchola is getting an array of integers as gift. He's weird, so he doesn't like having distinct integers in the same array and he only likes prime numbers. That's why he believes that he might need to fix the array after receiving it by turning all elements into the same prime number.

Sanchola is also very lazy and wants to do that using the minimum number of operations. In one operation Sanchola can either increase or decrease a single element of the array by one.

Given the array that he received as a gift, help Sanchola figuring out the minimum number of operations required to fix the array.

Input

The first line contains a single integer N

(1≤N≤105)

, indicating the length of the array.

The second line contains N

integers a1, a2, ..., an (1≤N≤109), indicating the elements of the array a

Output

In a single line output the minimum number of operations to satisfy Sanchola.

Examples

Input

3
2 3 10

Output

Input

2
1 1000000000

Output

999999999

Input

4
3 5 7 11

Output

#include <bits/stdc++.h>
using namespace std;
int prime(int x)
{
if(x==1||x==0)
return 0;
else if(x==2)
return 1;
else
{
int i;
for(i=2; i<=sqrt(x); i++)
if(x%i==0)
break;
if(i>sqrt(x))
return 1;
else
return 0;
}
}
int main()
{
int n;
long long d,i,j;
cin>>n;
int a[100010];
for(i=0; i<n; i++)
cin>>a[i];
sort(a,a+n);
if(n%2==0)
{
d=(a[n/2]+a[n/2-1])/2;
}
else
d=a[n/2];
long long int
sum=0;
i=0;
j=0;
while(1)
{
if(prime(d+i)==1)
break;
i++;
}
while(1)
{
if(prime(d-j)==1||d==j)
break;
j++;
}
long long int num=0;
for( int k=0; k<n; k++)
sum+=abs(a[k]-d-i);
if(j!=d)
for( int k=0; k<n; k++)
num+=abs(a[k]-d+j);
if(j!=d)
{
sum=min(sum,num);
}
cout<<sum;
return 0;
}