Submission #377345

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <array>

using namespace std;

#define all(c) ((c).begin()), ((c).end())
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define REP(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;


template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
  return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
  os<<'[';
  rep(i,a.size()) os<<(i?" ":"")<<a[i];
  return os<<']';
}

int main() {
  int n; cin >> n;
  vector<int> h(n);
  map<int, int> is;
  rep(i, n) {
    cin >> h[i];
    is[h[i]] = i;
  }
  vector<int> sh = h;
  sort(all(sh));

  vector<int> tmp;
  tmp.reserve(1000000);
  map<int, int> bs;
  rep(i, n) {
    int e = h[n - i - 1];
    if (tmp.size() == 0) {
      tmp.push_back(e);
      bs[e] = 0;
    }
    else {
      auto it = lower_bound(all(tmp), e);
      tmp.insert(it, e);
      bs[e] = it - tmp.begin();
      // dump(bs[e]);
    }
  }

  if (is.size() != n) {
    cout << -1 << endl;
    return 0;
  }

  ll ans = 0;
  rep(i, n) {
    ll e = sh[i];
    ll c = (is[e] + bs[e] - i) * e;
    // dump(i);
    // dump(e);
    // dump(is[e]);
    // dump(bs[e]);
    // dump(c);
    ans += c;
  }

  cout << ans << endl;



  return 0;
}

Submission Info

Judge Result