//the numbers can be very large,so we take long
     static ArrayList<Long>li;
     static ArrayList<Long>lu;
    static long fairCut(int k1, ArrayList<Long> arr) {
        li=new ArrayList<Long>();
        lu=new ArrayList<Long>();
        Collections.sort(arr);
        System.out.println("sorted list is:"+arr);
        int n=arr.size();
        int k=Math.min(k1,n-k1);
        //li will always get the element at position at n/2
        // (doesnt matter whether n is even or odd)
        
        //if k is 1 then give li n/2th element and find absolute difference
        if(k==1){
li.add(arr.get(n/2));
arr.remove(n/2);
return calcResult(li,arr);
        }

        //if k is greater then 1,then we must make the 01010101         //combination
        //assume that li denotes 0 and lu denotes 1
        //now to ensure the combination,li must skip one element and take //the immediately following element 

        li.add(arr.get(n/2));
        //loc1 is a leftPointer and loc2 is rightPointer

        int loc=n/2,loc1=n/2,loc2=n/2;
        arr.set(n/2,(long)0);//change the position at n/2 to 0
        //this means that the element at this position has been given to li
        //then in the calcResult function,continue when this 0 is //encountered
        --k;
 
        while(k>1){
            //skipping elements is possible in both directions,left and right
            //loc1 will take every "other" element in the left direction
            //(this means that it will take element after skipping one //element)  similarly loc2 will take every other element in right direction

loc1=loc1-2;
loc2=loc2+2;
//adding 2 elements,one from both directions into li list
li.add(arr.get(loc1));
li.add(arr.get(loc2));
arr.set(loc1,(long)0);
arr.set(loc2,(long)0);
k-=2;//two more elements were addded to li's list so decrement k count
        }
if(k==0)//all the requisite elements have been obtained
return calcResult(li,arr);


else if (k==1){//now one element more is to be added 

//we will have to choose an element that gives minimum result
long x1=loc1-2;//x1 is index position of the element after skipping one //element from the current position in the left direction.

long x2=loc2+2;

long valueReplaced=-1;
long res1=Long.MAX_VALUE,res2=Long.MAX_VALUE;

if(x1>=0)//the position should ,ofcourse be >=0 to find it in the given list
{
    //now we are calculating result using x1
li.add(arr.get((int)x1));
valueReplaced=arr.get((int)x1);//this variable will be used later
//it stores the value that will be replaced in the original array list
arr.set((int)x1,(long)0);
System.out.println("li arr is:"+li+"and arr is:"+arr);
res1=calcResult(li,arr);//res1 has the result when element at x1 position //is chosen

}
if(x2<=arr.size()-1)//x2 should evidently be <=0 to find it
//in the given arrayList
{
    System.out.println("li array is:"+li+"and original array is:"+arr);
if(valueReplaced==-1){
    //x1 is less than 0,no changes took place
//so we continue normally 
li.add(arr.get((int)x2));
arr.set((int)x2,(long)0);
res2=calcResult(li,arr);

//res2 is the result obtained when we choose element at x2 in the li list
}
else{
    //element at position x1 was used to find the result
    //so we must restore the list to its previous state

li.remove(li.size()-1);
arr.set((int)x1,valueReplaced);
li.add(arr.get((int)x2));
arr.set((int)x2,(long)0);
res2=calcResult(li,arr);
}
}//end of x2 if

System.out.println("li list is:"+li);
System.out.println("arr list is:"+arr);
return Math.min(res1,res2);
//return the minimum value obtained by adding elements at position 
//x1 or x2 to the li list
}//end of else if
return 0;
    }//end of func

public static long calcResult(ArrayList<Long> liArr,ArrayList<Long> luArr){

long sum=0;
for(int i=0;i<liArr.size();i++){
    for(int j=0;j<luArr.size();j++){
        if(luArr.get(j)==0)//do not calculate for this as it has been added to //li list
        continue;
        else
        sum+=Math.abs(liArr.get(i)-luArr.get(j));
    }
}
return sum;
}