#include <bits/stdc++.h> using namespace std; template<typename T> inline void Read(T &x) { x=0; char ch(getchar()); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); } #define ll long long ll n,ans; struct node { ll id,val; friend bool operator < (node a, node b) { return a.val<b.val; } friend bool operator <= (node a, node b) { return a.val<=b.val; } friend ll operator - (node x, node b) { return x.id-b.id; } } a[1000010]; deque<node>dq,by; int main() { dq.clear(),by.clear(); Read(n); for(ll i=1; i<=n; i++) Read(a[i].val),a[i].id=i; for(ll i=1; i<=n; i++) { //如果前面的比当前小，压到另外一个队列 node x; while(dq.size() && dq.front()<=a[i]) x=dq.front(),dq.pop_front(),by.push_back(x); dq.push_back(a[i]); ans+=a[i]-dq.front(); while(by.size()) x=by.back(),by.pop_back(),by.push_front(x); } cout.tie(0); cout<<ans<<endl; return 0; } /* 10 2 3 5 12 2 2 3 5 2 13 22 */