#include <bits/stdc++.h> using namespace std; #define ll long long mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } const ll INF = 1e18; const ll mod = 1e9 + 7; ll binpow(ll base, ll exp, ll mod) { ll ans = 1; ll mult = base; while(exp) { if(exp & 1) ans = (ans * mult) % mod; mult = (mult * mult) % mod; exp >>= 1; } return ans; } ll gcd(ll a, ll b) { if(b == 0) return a; return gcd(b, a%b); } const int N = 1e6 + 5; int arr[N]; pair<int, int> sorted_indices[N]; pair<int, int> queries[N]; int queries_ans[N]; inline ll valid_paths_in_length(ll len) { return len * (len + 1) / 2; } ll ans = 0; struct DSU { int up[N]; DSU() { memset(up, 0, sizeof(up)); } int find(int x) { if(up[x] < 0) return x; return (up[x] = find(up[x])); } bool unite(int a, int b) { int set_a = find(a); int set_b = find(b); if(set_a == set_b) return false; if(up[set_a] > up[set_b]) swap(set_a, set_b); ans -= valid_paths_in_length(-up[set_a]); ans -= valid_paths_in_length(-up[set_b]); up[set_a] += up[set_b]; up[set_b] = set_a; ans += valid_paths_in_length(-up[set_a]); return true; } void activate(int id) { //cout << "Activated " << id << "\n"; up[id] = -1; ans++; // Try to unite with adjacent ones if(id > 0 && up[id-1] != 0) unite(id, id-1); if(up[id+1] != 0) unite(id, id+1); } }; DSU dsu; void solve() { int n, q; cin >> n >> q; for(int i = 0; i < n; i++) { cin >> arr[i]; sorted_indices[i] = {arr[i], i}; } for(int i = 0; i < q; i++) { cin >> queries[i].first; queries[i].second = i; } sort(sorted_indices, sorted_indices + n); sort(queries, queries + q); int l = 0; for(int i = 0; i < q; i++) { while(l < n && sorted_indices[l].first <= queries[i].first) { dsu.activate(sorted_indices[l].second); l++; } queries_ans[queries[i].second] = ans; } for(int i = 0; i < q; i++) cout << queries_ans[i] << "\n"; } int main() { //freopen("COLLECT.INP", "r", stdin); //freopen("COLLECT.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tests = 1; //cin >> tests; while(tests--) solve(); }