#include <bits/stdc++.h>
using namespace std;
int n, cant1, cant2, cant3;
long long int e1, e2, e3, a[100010], C[100010][5];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int(i) = (int)(0); (i) < (int)(n); (i)++) cin >> a[i];
  sort(a, a + n);
  e1 = a[0];
  e2 = a[1];
  e3 = a[2];
  cant1 = cant2 = cant3 = 0;
  for (int(i) = (int)(0); (i) < (int)(n); (i)++) {
    if (a[i] == e1) cant1++;
    if (a[i] == e2) cant2++;
    if (a[i] == e3) cant3++;
  }
  for (int(i) = (int)(0); (i) < (int)(100010); (i)++) C[i][0] = 1;
  C[1][1] = C[2][2] = C[3][3] = 1;
  for (int(i) = (int)(0); (i) < (int)(100010); (i)++)
    for (int(j) = (int)(1); (j) < (int)(i); (j)++) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      if (j == 3) break;
    }
  if (e1 == e3)
    cout << C[cant1][3] << '\n';
  else {
    if (e1 == e2)
      cout << C[cant1][2] * cant3 << '\n';
    else {
      if (e2 == e3)
        cout << cant1 * C[cant2][2] << '\n';
      else
        cout << cant1 * cant2 * cant3 << '\n';
    }
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

After returning from the army Makes received a gift — an array a consisting of n positive integer numbers. He hadn't been solving problems for a long time, so he became interested to answer a particular question: how many triples of indices (i, j, k) (i < j < k), such that ai·aj·ak is minimum possible, are there in the array? Help him with it!

Input

The first line of input contains a positive integer number n (3 ≤ n ≤ 105) — the number of elements in array a. The second line contains n positive integer numbers ai (1 ≤ ai ≤ 109) — the elements of a given array.

Output

Print one number — the quantity of triples (i, j, k) such that i, j and k are pairwise distinct and ai·aj·ak is minimum possible.

Examples

Input

4
1 1 1 1


Output

4


Input

5
1 3 2 3 4


Output

2


Input

6
1 3 3 1 3 2


Output

1

Note

In the first example Makes always chooses three ones out of four, and the number of ways to choose them is 4.

In the second example a triple of numbers (1, 2, 3) is chosen (numbers, not indices). Since there are two ways to choose an element 3, then the answer is 2.

In the third example a triple of numbers (1, 1, 2) is chosen, and there's only one way to choose indices.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, cant1, cant2, cant3;
long long int e1, e2, e3, a[100010], C[100010][5];
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  for (int(i) = (int)(0); (i) < (int)(n); (i)++) cin >> a[i];
  sort(a, a + n);
  e1 = a[0];
  e2 = a[1];
  e3 = a[2];
  cant1 = cant2 = cant3 = 0;
  for (int(i) = (int)(0); (i) < (int)(n); (i)++) {
    if (a[i] == e1) cant1++;
    if (a[i] == e2) cant2++;
    if (a[i] == e3) cant3++;
  }
  for (int(i) = (int)(0); (i) < (int)(100010); (i)++) C[i][0] = 1;
  C[1][1] = C[2][2] = C[3][3] = 1;
  for (int(i) = (int)(0); (i) < (int)(100010); (i)++)
    for (int(j) = (int)(1); (j) < (int)(i); (j)++) {
      C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
      if (j == 3) break;
    }
  if (e1 == e3)
    cout << C[cant1][3] << '\n';
  else {
    if (e1 == e2)
      cout << C[cant1][2] * cant3 << '\n';
    else {
      if (e2 == e3)
        cout << cant1 * C[cant2][2] << '\n';
      else
        cout << cant1 * cant2 * cant3 << '\n';
    }
  }
  return 0;
}

```