#include <bits/stdc++.h>   using namespace std;   const long long N = 1e6 + 7;   long long n, q;   long long a[N];   long long l[N], r[N];   void read() {     cin >> n >> q;     for (long long i = 0; i < n; ++i) cin >> a[i];     for (long long i = 0; i < q; ++i) cin >> l[i];     for (long long i = 0; i < q; ++i) cin >> r[i];     for (long long i = 0; i < q; ++i) {       --l[i];       --r[i];     }   }   long long ans[N];   long long link[N];   vector<long long> add[N], del[N];   long long f[N], fcnt[N];   void addf(long long i) {     long long t = i;     for (; i < N; i |= (i + 1)) {       f[i] += t;     }   }   void addfcnt(long long i) {     for (; i < N; i |= (i + 1)) {       fcnt[i]++;     }   }   void add_(long long i) {     addf(i);     addfcnt(i);   }   long long getsum(long long i) {     long long ans = 0;     for (; i >= 0; i = (i & (i + 1)) - 1) {       ans += f[i];     }     return ans;   }   long long getcnt(long long i) {     long long ans = 0;     for (; i >= 0; i = (i & (i + 1)) - 1) {       ans += fcnt[i];     }     return ans;   }   long long getmax(long long x) {     return getcnt(x) * x + getsum(N - 1) - getsum(x);   }   long long pref[N];   void kek() {     for (long long i = 0; i < N; ++i) {       f[i] = fcnt[i] = 0;     }     for (long long i = 0; i < q; ++i) {       ans[i] += pref[r[i] + 1] - pref[l[i]];     }     for (long long i = 0; i < N; ++i) f[i] = fcnt[i] = 0;     for (long long i = 0; i < n; ++i) {       add[i].clear();       del[i].clear();     }     for (long long i = 0; i < n; ++i) link[i] = -1;     vector<long long> st;     for (long long i = n - 1; i >= 0; --i) {       while (st.size() && a[i] > a[st.back()]) {         link[st.back()] = i;         st.pop_back();       }       st.push_back(i);     }     for (long long i = 0; i < q; ++i) {       add[r[i]].push_back(i);       if (l[i]) del[l[i] - 1].push_back(i);     }     for (long long i = 0; i < n; ++i) {       add_(link[i] + 1);       for (long long e : add[i]) {         ans[e] -= getmax(l[e]);       }       for (long long e : del[i]) {         ans[e] += getmax(l[e]);       }     }   }   void solve() {     for (long long i = 0; i < n; ++i) {       pref[i + 1] = pref[i] + i;     }     for (long long i = 0; i < q; ++i) {       ans[i] = r[i] - l[i] + 1;     }     kek();     reverse(a, a + n);     for (long long i = 0; i < q; ++i) {       l[i] = n - 1 - l[i];       r[i] = n - 1 - r[i];       swap(l[i], r[i]);     }     kek();   }   void print() {     for (long long i = 0; i < q; ++i) cout << ans[i] <<    ;     cout <<   n ;   }   signed main() {     ios_base::sync_with_stdio(0);     cin.tie(0);     cout.precision(20);     read();     solve();     print();   }   