#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll n, q;
cin >> n >> q;
vector<ll> v(n);
for (ll i = 0; i < n; i++) cin >> v[i];
// Preprocess segments
vector<pair<ll, ll>> segments; // {max_value_in_segment, count_of_subarrays}
ll i = 0;
while (i < n) {
if (i < n && v[i] == LLONG_MAX) {
i++;
continue;
}
ll j = i;
ll max_val = v[i];
while (j < n && v[j] != LLONG_MAX) {
max_val = max(max_val, v[j]);
j++;
}
ll len = j - i;
ll count = len * (len + 1) / 2;
segments.emplace_back(max_val, count);
i = j;
}
// For this specific problem, we want segments where ALL values < query
// So we actually need to process the array differently:
// Let's process and track contiguous segments where values are < some threshold
// Instead of the above, do this:
vector<pair<ll, ll>> segs; // {max_value_in_segment, count_of_subarrays}
i = 0;
while (i < n) {
if (v[i] == -1) { i++; continue; }
if (v[i] >= 1e9 + 1) { i++; continue; }
if (v[i] < 0) { i++; continue; }
if (v[i] != LLONG_MAX) {
ll j = i;
ll min_value = v[i];
while (j < n && v[j] != LLONG_MAX) {
min_value = max(min_value, v[j]);
j++;
}
ll len = j - i;
ll cnt = len * (len + 1) / 2;
segs.push_back({min_value, cnt});
i = j;
} else {
i++;
}
}
// Instead of doing the above with undefined values, we’ll use:
// Step 1: Find all contiguous segments where values are strictly LESS than a given value
vector<pair<ll, ll>> thresholds; // {max_element_in_segment, count_of_subarrays}
i = 0;
while (i < n) {
if (v[i] >= 0) {
ll j = i;
ll max_elem = v[i];
while (j < n && v[j] >= 0) {
max_elem = max(max_elem, v[j]);
j++;
}
ll len = j - i;
ll cnt = len * (len + 1) / 2;
thresholds.push_back({max_elem, cnt});
i = j;
} else {
i++;
}
}
// But better: treat values >= threshold as break points
vector<pair<ll, ll>> seg_data; // {max_in_segment, count}
i = 0;
while (i < n) {
if (v[i] < 0) { i++; continue; }
if (v[i] >= 0) {
ll j = i;
ll max_v = v[i];
while (j < n && v[j] >= 0) {
max_v = max(max_v, v[j]);
j++;
}
ll len = j - i;
ll cnt = len * (len + 1) / 2;
seg_data.push_back({max_v, cnt});
i = j;
}
}
// More directly: For given array, break into segments where values are all < threshold (to be determined)
// Better to preprocess for each segment: record the maximum value (since segment is valid only if all values < a)
vector<pair<ll, ll>> segs_final; // {max_value_in_segment, count}
i = 0;
while (i < n) {
if (v[i] < 0) { i++; continue; }
ll j = i;
ll max_v = v[i];
while (j < n && v[j] >= 0) {
max_v = max(max_v, v[j]);
j++;
}
ll len = j - i;
ll cnt = len * (len + 1) / 2;
segs_final.push_back({max_v, cnt});
i = j;
}
// Sort segments by max_value in segment
sort(segs_final.begin(), segs_final.end());
// Build prefix sum
vector<ll> prefix_sum(segs_final.size());
for (size_t i = 0; i < segs_final.size(); i++) {
prefix_sum[i] = segs_final[i].second + (i > 0 ? prefix_sum[i - 1] : 0);
}
// Answer queries in log time
while (q--) {
ll a;
cin >> a;
// Find number of segments with max < a
auto it = upper_bound(segs_final.begin(), segs_final.end(), make_pair(a - 1, LLONG_MAX));
ll idx = distance(segs_final.begin(), it);
ll ans = (idx > 0 ? prefix_sum[idx - 1] : 0);
cout << ans << '\n';
}
return 0;
}
