Submission #3457690

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>
#include <set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

int A[200100];
int index[200100];
int main(){
    int N;
    cin >> N;
    ll ans = 0;
    REP(i,N){
        int a;
        cin >> a;
        A[i] = a;
        a--;
        index[a] = i;
    }
    
    set<int> s;
    s.insert(N);
    s.insert(-1);
    REP(i,N){
        int ind = index[i];
        set<int>::iterator itr = s.lower_bound(ind);
        int right = *itr - ind;
        itr--;
        int left = ind - *itr;
        ans += A[ind]*left*right; 
        s.insert(ind);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result