#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// Use long long for sums and potentially large values
typedef long long ll;

// Define a large enough value to represent infinity for the initial minimum comparison.
// Needs to be larger than any possible position value (which is N <= 10^5).
// Using 10^9 + 7, a common large prime, is clearly sufficient.
const ll INF = 1e9 + 7; 

// Structure for segment tree nodes
struct Node {
    ll min_val; // Stores the minimum value in the range [start, end] covered by this node
};

// Global variables
vector<ll> p; // Base array (conceptually) storing last seen positions p_0, ..., p_N. p[0] = r, p[i] = last_pos(i, r) for i > 0. We don't actually need to store p explicitly since the segment tree holds the values.
vector<Node> tree; // Segment tree array
int N; // Length of the input array A
int base_size; // The number of logical indices we need to cover: 0 to N, so N+1 indices.
int tree_nodes_allocated_size; // Number of leaves in the segment tree (smallest power of 2 >= base_size)
int tree_array_size; // Actual size allocated for the segment tree array (usually 2 * tree_nodes_allocated_size)

// Function to build the segment tree
// node: current node index in tree array (1-based indexing is common)
// start, end: range of indices covered by this node in the conceptual base array
void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node initialization. If index 'start' is within the logical range [0, N], 
        // initialize with p[start] (which is 0 initially). Otherwise, use 0 for padding leaves.
        if (start < base_size) {
             // Initially all last positions are 0.
             tree[node] = {0}; 
        } else {
             // This part handles indices beyond N used for padding to power of 2 size
             tree[node] = {0}; // Padding leaves are initialized to 0
        }
    } else {
        int mid = start + (end - start) / 2;
        // Recursively build left and right children
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        // Combine results: the minimum value in this node is the minimum of its children
        tree[node] = {min(tree[2 * node].min_val, tree[2 * node + 1].min_val)};
    }
}

// Function to update a value in the segment tree (point update)
// node: current node index
// start, end: range covered by this node
// idx: index in the conceptual base array p to update (0 <= idx <= N)
// val: new value (the position r)
void update(int node, int start, int end, int idx, ll val) {
    // If index is outside the node's range, return. This handles recursive calls correctly.
    if (start > idx || end < idx) {
        return;
    }

    // Leaf node corresponds to idx
    if (start == end) {
        tree[node].min_val = val;
    } else {
        // Recursive step: decide whether to go left or right
        int mid = start + (end - start) / 2;
        if (idx <= mid) { // Check if index is within left child range
            update(2 * node, start, mid, idx, val);
        } else { // Index must be in right child range
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        // After update in child, update current node's minimum based on children
        tree[node].min_val = min(tree[2 * node].min_val, tree[2 * node + 1].min_val);
    }
}

// The custom query function to compute the sum T_r = sum_{k=1}^{N+1} min(p_0, ..., p_{k-1})
// node: current node index
// start, end: range of indices covered by this node in the conceptual base array
// current_min: the minimum value found in p[0...start-1] passed down from parent/ancestor calls
ll query_sum(int node, int start, int end, ll current_min) {
    
    // Clip the current node's range [start, end] to the relevant logical range [0, N].
    // Nodes/parts of nodes covering indices > N are irrelevant to the sum calculation.
    if (start >= base_size) {
         return 0; // This entire node range is outside [0, N]
    }
    int actual_end = min(end, base_size - 1); // Consider only indices up to N

    // Optimization: If the minimum value in this node's range [start, end] is already >= current_min,
    // then for all k such that k-1 is in [start, actual_end], the prefix minimum min(p_0, ..., p_{k-1})
    // will be determined by values before index start, which is captured by current_min.
    // The contribution to the total sum for this range is (number of relevant elements) * current_min.
    // The number of relevant elements is (actual_end - start + 1).
    if (tree[node].min_val >= current_min) {
        return (ll)(actual_end - start + 1) * current_min;
    }
    
    // Base case: Leaf node
    if (start == end) {
        // Check if this leaf index is within the valid range [0, N]
        if (start < base_size) {
            // The value at this leaf is p[start]. The prefix minimum up to index start is min(current_min, p[start]).
            // This corresponds to the term for k = start + 1 in the sum.
             return min(tree[node].min_val, current_min);
        } else {
             return 0; // Leaf index outside [0, N], contributes 0
        }
    }

    // Recursive step: Query left and right children
    int mid = start + (end - start) / 2;
    
    // Query left child. The current_min remains the same.
    ll left_sum = query_sum(2 * node, start, mid, current_min);
    
    // For the right child query, the new current_min needs to incorporate the minimum from the left child's range [start, mid].
    // This minimum is stored in the left child node `tree[2*node]`.
    ll new_current_min = min(current_min, tree[2 * node].min_val); 
    
    // Query right child with the updated current_min.
    ll right_sum = query_sum(2 * node + 1, mid + 1, end, new_current_min);
    
    // Total sum for this node's range is the sum from left and right children.
    return left_sum + right_sum;
}


int main() {
    // Faster I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;

    vector<int> A(N + 1); // Input array A (1-based indexing for problem statement)
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
    }

    // Initialize p array conceptually. We don't need the actual array p.
    // p size needed is N+1 to store indices 0 to N.
    base_size = N + 1; 
    
    // Calculate required size for segment tree leaves (power of 2)
    tree_nodes_allocated_size = 1;
    while (tree_nodes_allocated_size < base_size) {
        tree_nodes_allocated_size *= 2;
    }
    // Total nodes in segment tree array is typically 2*leaves - 1, use 2*leaves for 1-based index safety.
    tree_array_size = 2 * tree_nodes_allocated_size;
    tree.resize(tree_array_size);

    // Build the segment tree covering range [0, tree_nodes_allocated_size - 1]
    // Initial values are all 0 representing initial last positions.
    build(1, 0, tree_nodes_allocated_size - 1); 

    ll total_sum = 0; // Use long long for the final answer

    // Iterate through r from 1 to N, processing the array element A[r]
    for (int r = 1; r <= N; ++r) {
        // Update p[0] to r. This represents the current right endpoint r.
        // Updates operate on the segment tree covering the full allocated range [0, tree_nodes_allocated_size - 1]
        update(1, 0, tree_nodes_allocated_size - 1, 0, r);
        
        // Update p[A[r]] to r. A[r] is the value at index r. Use it as index into p array.
        // Constraint: 1 <= A[i] <= N. So A[r] is a valid index for p[1...N].
        update(1, 0, tree_nodes_allocated_size - 1, A[r], r);

        // Compute Tr = sum_{k=1}^{N+1} min(p_0, ..., p_{k-1}) using the custom query
        // Start query from root node (index 1), covering the full allocated range [0, tree_nodes_allocated_size - 1].
        // The query function internally handles restricting calculations to the logical range [0, N].
        ll Tr = query_sum(1, 0, tree_nodes_allocated_size - 1, INF);
        
        // Add Tr to the total sum
        total_sum += Tr;
    }

    // Output the final total sum
    cout << total_sum << endl;

    return 0;
}