/* FILE: triplette2.cpp   last change: 12-Sept-2012   author: Romeo Rizzi
 * an optimal (quadratic) solver for problem "triplette"
 */

#define NDEBUG   // NDEBUG definita nella versione che consegno
#include <cassert>
#ifndef NDEBUG
#  include <iostream>  // uso di cin e cout non consentito in versione finale
#endif
#include <fstream>
#include <climits>

using namespace std;

const int UNFEASIBLE = INT_MAX;
const int MAX_N = 10000;  // massima cardinalita' dell'insieme di numeri fornito in input
int n, vect[MAX_N];

   /* assumes the input integers have been sorted so that vect[0], ..., vect[n-1] is non-decreasing.
Once this is done, it can be proven that there always exists an optimal solution where the two rightmost elements of each triplet are consecutive.
We call these two elements the "head" of the triplet, and search for an optimum solution among those which have this structure (no head is split).
minCost[i][numHeads] will store the minimum cost of a partial solution which has placed numHeads full heads within vect[i], ..., vect[n-1].
Furthermore, vect[i] is bound to be either a tail or the first of the two elements of an head. 
In conclusion, no triplet has precisely one element within vect[i], ..., vect[n-1] and precisely numHeads triplets have at least 2 elements within 
vect[i], ..., vect[n-1] and we consider only the weight of these triplets.
*/

int minCostWithout[MAX_N +1][MAX_N/3 +1];

void swap(int &a, int &b) { int tmp = a; a = b; b = tmp; }

void sort(int vect[], int n) {
  if( n > 1 ) {
    for(int i = 0; i < n-1; i++)
      if( vect[n-1] < vect[i] )  swap(vect[n-1], vect[i]);
    sort(vect, n-1);
  }
}

#ifndef NDEBUG
void displayVect(int vect[], int n) {
  for(int i = 0; i < n; i++)  cout << vect[i] << " ";
  cout << endl;
}
#endif

int main() {
  ifstream fin("input.txt"); assert(fin);
  fin >> n;
  for(int i = 0; i < n; i++)  fin >> vect[i];
  fin.close(); //displayVect(vect, n);
  sort(vect, n); //displayVect(vect, n);

  minCostWithout[n][0] = 0; minCostWithout[n-1][1] = minCostWithout[n-1][0] = UNFEASIBLE;
 
  for(int i = n-2; i >= 0; i--)
    for(int j = n/3 +1; j >= 0; j--) { 
        if( 2*j > n-i)  minCostWithout[i][j] = UNFEASIBLE; //troppe teste in suffisso di soli n-i elementi
        else if( j < (n-i +2)/3 )  minCostWithout[i][j] = UNFEASIBLE;
        else {
	    minCostWithout[i][j] = minCostWithout[i+1][j];
            if( minCostWithout[i+2][j-1] != UNFEASIBLE )
               minCostWithout[i][j] =  min(
                                     minCostWithout[i][j],
                                     minCostWithout[i+2][j-1] + (vect[i]-vect[i+1])*(vect[i]-vect[i+1]) 
			           );
            #ifndef NDEBUG
	    cout << "minCostWithout[" << i << "][" << j << "] = " << minCostWithout[i][j] << endl;
            #endif
        }
	//cout << "WIDER minCost[" << i << "][" << j << "] = " << minCost[i][j] << endl; 
    }

  ofstream fout("output.txt"); assert(fout);
  fout << minCostWithout[0][n/3] << endl;
  fout.close();
  return 0;
}