Profesor matematike je postavio Dragančetu sledeći zadatak. Na osnovu datog niza brojeva a₁, a₂, ..., a_n, Draganče treba da za svaku trojku indeksa (i, j, k), gde je 1 ≤ i < j < k ≤ n, napiše na tabli najveći od brojeva a_i, a_j i a_k. Zatim treba da izračuna ostatak koji daje zbir svih brojeva koji su napisani na tabli pri deljenju sa 10007. Profesor je obećao Dragančetu peticu za kraj školske godine, ako dobije tačno rešenje pre kraja časa. Pomozite Dragančetu da što brže dobije tačan rezultat.

Ulaz:

(Ulazni podaci se nalaze u datoteci trojke.in) U prvom redu ulazne datoteke nalazi se broj n (3 ≤ n ≤ 30000). U sledećih n redova se nalaze celi brojevi a₁, a₂, ..., a_n, pri čemu je -100000 ≤ a_i ≤ 100000.

Izlaz:

(Izlazne podatke upisati u datoteku trojke.out) U prvom i jedinom redu izlazne datoteke ispisati sumu brojeva napisanih na tabli po modulu 10007.

Primer 1:

4
3
-1
2
2

11

Objašnjenje.

Sve trojke niza brojeva su: (3, -1, 2), (3, -1, 2), (3, 2, 2), (-1, 2, 2). Na tabli su napisani brojevi 3, 3, 3, 2, pa je rešenje u ovom slučaju 11.

Primer 2:

6
8
-10
4
5
2
6

135

/*
  DRZAVNO TAKMICENJE 2008
  ZADATAK: trojke
  AUTOR: Aleksandar i Andreja Ilic, Nis

  Za svaku uredjenu strago rastucu trojku indeksa (i, j, k)
  treba sabrati max (a_i, a_j, a_k). Na pocetku sortiramo niz
  u nerastucem poredtku. Broj a [1] je najveci u svakoj trojci u
  kojoj se nalazi - dakle tacno (n - 1)(n - 2) / 2 puta. Slicno
  dobijamo da se a [k] pojavljuje (n - k)(n - k - 1) / 2 puta.
    
    Pri mnozenju moramo paziti da ne dodje do prekoracenja,
  tako da posle svakog sabiranja i mnozenja uzimamo ostatak pri
  deljenju sa 10007.

    Vremenska slozenost gore navedenog algoritma je O(n log n),
  dok je memorijska O (n).
*/

#include <stdlib.h>
#include<stdio.h>
#include <time.h> 
#define maxN 30005
#define mod 10007

int n, sol, a [maxN];
FILE *in, *out;

  // Permutovanje niza
  void mixArray()
  {
        srand(time(0));
    for (int k = 1; k < n; k++)
    {
      int x = rand() % k;
      int tmp = a [x]; 
            a [x] = a [k]; 
            a [k] = tmp;
    }
  }

  // Sortiranje niza
  void Sort (int l,  int d)
  {
    int tmp, pivot, i, j;
    if (l < d)
    {
      pivot = a [(l + d) / 2];
      i = l; 
      j = d;
      do
      {
        while (a [i] > pivot) i++;
        while (a [j] < pivot) j--;
        if (i <= j)
        {
             tmp = a [i]; a [i] = a [j]; a [j] = tmp;
          i++; j--;
        }
      }
      while (i <= j);
      Sort (l, j);
      Sort (i, d);
      }
  }

  // Glavna fja
  void Solve()
  {
        mixArray();
    Sort(0, n - 1);
    for (int i = 0; i < n; i++)
    {
        a [i] = a [i] % mod;
        if (a [i] < 0)
           a [i] += mod;
        }
    sol = 0;
    for (int i = 0; i < n - 2; i++)
    {
            int tmp = (n - i - 1) * (n - i - 2) / 2;
            if (tmp > mod)
               tmp = tmp % mod;
            sol += tmp * a [i];
            if (sol > mod)
               sol = sol % mod;
    }
  }

    // Unos podataka
  void InPut()
  {
    in = fopen ("trojke.in", "r");
    fscanf (in, "%d", &n);
    for (int i = 0; i < n; i++)
      fscanf (in, "%d", &a [i]);
    fclose(in);
  }

  // Ispis resenja
  void OutPut()
  {
    out = fopen ("trojke.out", "w");
    fprintf (out, "%d\n", (int) sol);
    fclose(out);
  }

int main()
{
  InPut();
  Solve();
  OutPut();
  return 0;
}