#include <string>
#include <vector>
#include <deque>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
 
class Graph {
  public:
    vector <class Node *> N;          // The nodes in the graph
    deque <class Node *> L;           // This is the list of nodes with no incoming edges.
    vector <int> A;                   // The original input.
    void Make_Graph();                // Method to create the graph from the input.
    long long TS();                   // Method to perform the topological sort
};

class Node {
  public:
    int ID;                           // The node's id (its index in Graph::N)
    int Value;                        // The node's value (A[ID])
    vector <Node *> Adj;              // Adjacency list
    int NumIncident;                  // Number of edges incident to the node.
    long long Paths;                  // Number of paths to N
};

/* Make Graph creates the graph from the input vector. */

void Graph::Make_Graph()
{
  int i, j;
  Node *n, *to;
  int bigval;                         // Bigval is a sentinel that we use to create the
                                      // adjacency lists.

  /* First create all of the nodes.  Initialize the values stored in each node. */

  N.resize(A.size(), NULL);

  for (i = 0; i < A.size(); i++) {
    n = new Node;
    n->ID = i;
    n->Value = A[i];
    n->Paths = 0;
    n->NumIncident = 0;
    N[i] = n;
  }

  /* Create the adjacency list for each node */

  for (i = 0; i < N.size(); i++) {
    bigval = 1000000001;
    n = N[i];
    for (j = i+1; j < N.size(); j++) {
      to = N[j];
      if (to->Value > n->Value && to->Value < bigval) {
        n->Adj.push_back(to);
        bigval = to->Value;
        to->NumIncident++;
      }
    }
  }

  /* For each node that has no incident edges, push the node onto the list L */

  for (i = 0; i < N.size(); i++) {
    if (N[i]->NumIncident == 0) {
      L.push_back(N[i]);
      N[i]->Paths = 1;
    }
  }

  /* This loop prints out the graph for debugging. */

  for (i = 0; i < N.size(); i++) {
    n = N[i];
    printf("Node %d: NumIncident: %d.  Adj:", i, n->NumIncident);
    for (j = 0; j < n->Adj.size(); j++) {
      printf(" %d", n->Adj[j]->ID);
    }
    printf("\n");
  }
}

/* TS performs the topological sort to count the paths from 
   nodes with no incoming edges to nodes with no outgoing edges. */

long long Graph::TS()
{
  long long RV;
  Node *n, *t;
  int i;

  RV = 0;

  while (!L.empty()) {
 
    /* Process the first node on L, and then delete it.  We use a deque for
       this, because it implements push_back() and pop_front() in constant time */

    n = L[0];
    L.pop_front();

    /* If the node is terminal (has no outgoing edges), then add its
       number of paths to the overall return value. */

    if (n->Adj.size() == 0) RV += n->Paths;

    /* Process the adjacency list, adding my paths to each node on my adjacency
       list, and then "erasing" the edge by decrementing NumIncident on the 
       node that the edge is going to.  If that number is zero, then push the node
       onto L. */

    for (i = 0; i < n->Adj.size(); i++) {
      t = n->Adj[i];
      t->Paths += n->Paths;
      t->NumIncident--;
      if (t->NumIncident == 0) L.push_back(t);
    }
  }

  return RV;
}

class IncreasingSubsequences {
  public:
    long long count(vector <int> a);
};

/* The main method to solve the topcoder problem simply creates the graph,
   then returns the return value of TS. */

long long IncreasingSubsequences::count(vector <int> a)
{
  Graph G;

  G.A = a;
  G.Make_Graph();
  return G.TS();
}