#include <iostream> #include <set> #include <vector> #include <algorithm> #pragma GCC target ("avx2") #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") using namespace std; typedef int ll; #define endl "\n" int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t = 1; //cin >> t; while(t--) { ll n, q; cin >> n >> q; ll a[n + 1], i; vector<pair<ll, ll>>sapxep1; for(i = 1; i <= n; i++) { cin >> a[i]; sapxep1.push_back(make_pair(a[i], i)); } sort(sapxep1.begin(), sapxep1.end()); long long ans[q + 1]; vector<pair<ll, ll>>sapxep; for(i = 1; i <= q; i++) { ll val; cin >> val; sapxep.push_back(make_pair(val, i)); } sort(sapxep.begin(), sapxep.end()); set<ll>pos; for(i = 1; i <= n; i++) { pos.insert(i); } pos.insert(0); pos.insert(n + 1); long long ans1 = 0, vtri = 0; ll siz = sapxep.size(); ll siz1 = sapxep1.size(); for(i = 0; i < siz; i++) { ll pos1 = upper_bound(sapxep1.begin(), sapxep1.end(), make_pair(sapxep[i].first, 0)) - sapxep1.begin(); while(vtri < pos1) { auto it = pos.lower_bound(sapxep1[vtri].second); auto it1 = it; auto it2 = it; it1--; it2++; ans1 += (long long)(*it2 - *it) * (long long)(*it - *it1); vtri++; pos.erase(it); //cout << vtri << " " << ans1 << " " << i << " " << *it << " " << *it1 << " " << *it2 << endl; } ans[sapxep[i].second] = ans1; } for(i = 1; i <= q; i++) { cout << ans[i] << endl; } cout << endl; } #ifndef ONLINE_JUDGE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; } // Author: tryharderforioi100