#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
#include<utility>
#include<cstdlib>
#include<typeinfo>
#include<stack>
#include<cassert>
#define int long long int
using namespace std;
#define INT_MAX 1000000005
#define INF 1000000005
const int MAX_N = 1 << 17;
#define REP(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

template<class T>
class MinOp{
public:
  T operator () ( T a , T b ){ return min( a , b ); }
};

template<class T>
class LtOp{
public:
  bool operator () ( T a , T b ){ return a < b; }
};

// sparse table
// static range semigroup query
// time complexity: <O(n log n), O(1)>
// OpFunc is binary operator: T x T -> T
template<typename T, typename OpFunc>
struct SparseTable{
  OpFunc op;
  int size;
  vector<int> lg;
  vector<vector<T> > table;
  void init( const vector<T> &array, OpFunc opfunc ){
    int n = array.size();
    op = opfunc;
    
    lg.assign( n + 1 , 0 );
    for( int i = 1; i <= n; i++ ){
      lg[i] = 31 - __builtin_clz( i );
    }

    table.assign( lg[n] + 1, array );
    for( int i = 1; i <= lg[n]; i++ ){
      for( int j = 0; j < n; j++ ){
        if( j + (1<<(i-1)) < n ){
          table[i][j] = op( table[i-1][j] , table[i-1][j+(1<<(i-1))] );
        } else {
          table[i][j] = table[i-1][j];
        }
      }
    }
  }
  T query( int l , int r ){
    assert( l < r );
    return op( table[ lg[r-l] ][l], table[ lg[r-l] ][r-(1<<lg[r-l])] );
  }
};


// plus minus one Range Minimum Query
// time complexity: <O(n), O(1)>
struct PMORMQ{
  vector<int> a;
  SparseTable<pair<int,int>,MinOp<pair<int,int> > > sparse_table;
  vector<vector<vector<int> > > lookup_table;
  vector<int> block_type;
  int block_size, n_block;
  void init( const vector<int> &array ){
    a = array;
    int n = a.size();
    block_size = max( 1, ( 31 - __builtin_clz( n ) ) / 2 );
    while( n % block_size != 0 ){
      a.push_back( a.back() + 1 );
      n++;
    }
    n_block = n / block_size;

    vector<pair<int,int> > b( n_block, make_pair( INT_MAX, INT_MAX ) );
    for( int i = 0; i < n; i++ ){
      b[i/block_size] = min( b[i/block_size], make_pair( a[i], i ) );
    }
    sparse_table.init( b, MinOp<pair<int,int> >() );

    block_type.assign( n_block, 0 );
    for( int i = 0; i < n_block; i++ ){
      int cur = 0;
      for( int j = 0; j < block_size-1; j++ ){
        int ind = i * block_size + j;
        if( a[ind] < a[ind+1] ){
          cur |= 1 << j;
        }
      }
      block_type[i] = cur;
    }

    lookup_table.assign( 1 << (block_size-1), vector<vector<int> >( block_size, vector<int>( block_size+1 ) ) );
    for( int i = 0; i < (1<<(block_size-1)); i++ ){
      for( int j = 0; j < block_size; j++ ){
        int res = 0;
        int cur = 0;
        int pos = j;
        for( int k = j+1; k <= block_size; k++ ){
          lookup_table[i][j][k] = pos;
          if( i & ( 1 << (k-1) ) ){
            cur++;
          } else {
            cur--;
          }
          if( res > cur ){
            pos = k;
            res = cur;
          }
        }
      }
    }
  }
  int query( int l, int r ){ // return position
    assert( l < r );
    int lb = l / block_size;
    int rb = r / block_size;
    if( lb == rb ){
      return lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ r % block_size ];
    }
    int pl = lb * block_size + lookup_table[ block_type[lb] ][ l % block_size ][ block_size ];
    int pr = rb * block_size + lookup_table[ block_type[rb] ][0][ r % block_size ];
    int pos = pl;
    if( r % block_size > 0 && a[pl] > a[pr] ){
      pos = pr;
    }
    if( lb + 1 == rb ){
      return pos;
    }
    int sp = sparse_table.query( lb+1, rb ).second;
    if( a[pos] > a[sp] ){
      return sp;
    }
    return pos;
  }
};

// LCA
// time complexity: <O(n), O(1)>
struct LCA{
  int n;
  vector<vector<int> > G;
  PMORMQ rmq;
  int cnt;
  vector<int> depth, id, in;
  void init( int size ){
    n = size;
    G.assign( n, vector<int>( 0 ) );
  }
  void add_edge( int a , int b ){
    G[a].push_back( b );
    G[b].push_back( a );
  }
  void dfs( int x , int p , int d ){
    id[cnt] = x;
    depth.push_back( d );
    in[x] = cnt++;
    for( int v : G[x] ){
      if( v == p ){
        continue;
      }
      dfs( v , x , d+1 );
      id[cnt] = x;
      depth.push_back( d );
      cnt++;
    }
  }
  void precalc( int root ){
    cnt = 0;
    depth.clear();
    in.assign( n, -1 );
    id.assign( 2*n-1, -1 );
    dfs( root, -1, 0 );
    rmq.init( depth );
  }
  int lca( int a , int b ){
    int x = in[a];
    int y = in[b];
    if( x > y ){
      swap( x , y );
    }
    int pos = rmq.query( x, y + 1 );
    return id[pos];
  }
};

// static range min query
// time complexity: <O(n), O(1)>
// OpFunc is binary operator: T x T -> bool
template<typename T, typename OpFunc>
struct RMQ{
  int n;
  OpFunc op;
  vector<T> a;
  LCA lca;
  void construct_cartesian_tree(){
    lca.init( n );
    vector<int> p( n, -1 );
    stack<int> st;
    for( int i = 0; i < n; i++ ){
      int prv = -1;
      while( !st.empty() && op( a[i], a[st.top()] ) ){
        prv = st.top();
        st.pop();
      }
      if( prv != -1 ){
        p[prv] = i;
      }
      if( !st.empty() ){
        p[i] = st.top();
      }
      st.push( i );
    }
    int root = -1;
    for( int i = 0; i < n; i++ ){
      if( p[i] != -1 ){
        lca.add_edge( i, p[i] );
      } else {
        root = i;
      }
    }
    lca.precalc( root );
  }
  void init( const vector<T> &array, OpFunc opfunc ){
    a = array;
    n = a.size();
    op = opfunc;
    construct_cartesian_tree();
  }
  T query( int l, int r ){
    assert( l < r );
    int p = lca.lca( l, r-1 );
    return a[p];
  }
};

RMQ<int,LtOp<int> > rmq;


// stack extension
// from http://www.colun.net/archives/547
// this code is not included in the (MIT) license
#define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
#define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

signed main()
{
int n;
std::cin >> n;
std::vector<int> a;
std::vector<int> check(n + 1,INF);
check.push_back(INF);
for( int i = 0; i < n; i++ ){
	int temp;
	std::cin >> temp;
  a.push_back(temp);
  check[temp] = i;
}
std::set<int> se;
int sum = 0;
for(int i = 1; i <= n; i++){
    int r,l;
    int now = check[i];
    se.insert(now);
    l = 0;
    r = n - 1;
    auto it = se.find(now);
    if(it != se.begin()){
        auto lit = std::next(it,-1);
        l = *lit + 1;
    }
    if(it != std::next(se.end(), -1)){
        auto rit = std::next(it,1);
        r = *rit - 1;
    }
    sum += (now - l + 1) * (r - now + 1) * i;
}

std::cout << sum << std::endl;
return 0;
}

Measured memory_bytes: 13668