output_description: Print the answer.
  
  Note that the answer may not fit into a 32-bit integer.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      a_1 a_2 ... a_N
attempt: #include<iostream>
  #include<iomanip>
  #include<cmath>
  #include<string>
  #include<cstring>
  #include<vector>
  #include<list>
  #include<algorithm>
  #include<map>
  #include<set>
  #include<queue>
  #include<stack>
  using namespace std;
  typedef long long ll;
  #define fi first
  #define se second
  #define mp make_pair
  #define mt make_tuple
  #define pqueue priority_queue
  const int inf=1e9+7;
  const ll mod=1e9+7;
  const ll mod1=998244353;
  const ll big=1e18;
  const double PI=2*asin(1);
  
  int main() {
    int N;
    cin>>N;
    int a[N];
    int tmptmp;
    for(int i=0;i<N;++i) {
      cin>>tmptmp;
      tmptmp--;
      a[tmptmp] = i;
    }
    set<ll> st;
    st.insert(-1);
    st.insert(N);
    auto tmp=st.begin(), tmp1=st.begin(), tmp2=st.begin();
    ll ans = 0;
    for(ll i=0;i<N;++i) {
      st.insert(a[i]);
      tmp = st.find(a[i]);
      tmp1 = st.find(a[i]);
      tmp1--;
      tmp2 = st.find(a[i]);
      tmp2++;
      ans += (i+1)*(*tmp-*tmp1)%mod*(*tmp2-*tmp)%mod;
      ans %= mod;
    }
    cout<<ans<<endl;
  }
  
  
problem_description: Statement
  
  One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from
  his friend.
  
  Find the following:
  
  ![](https://atcoder.jp/img/agc005/520049e1a049bb9810b398b35d7dcb7f.png)
samples: [{"input": "3\n    2 1 3", "output": "9\n    \n\n* * *"}, {"input": "4\n    1 3 2 4", "output": "19\n    \n\n* * *"}, {"input": "8\n    5 4 8 1 2 6 7 3", "output": "85"}]