#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6+5;
int calc(pair<int,int> p){
int len = p.second - p.first +1;
return (len*(len+1))/2;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m; cin>>n>>m;
vector<int> v(n); for(int& i : v) cin>>i;
vector<int> b(m); for(int& i : b) cin>>i;
set<pair<int,int>> segs; segs.insert({0,n-1}); segs.insert({n,n});
vector<vector<int>> ST(MAXN);
for(int i = 0; i<m; i++) ST[b[i]].push_back(i); // indexed one more
for(int i = 0; i<n; i++) ST[v[i]].push_back(-i-1);
int ans = n*(n+1)/2;
vector<int> q(m);
// cerr<<MAXN<<endl;
for(int j = MAXN-1; j>=0; j--){
for(auto i : ST[j]){
if(i < 0){
// cur seg
if(segs.size() == 0) continue;
int x = -i -1;//i+1
pair<int,int> p = {x, n};
auto it = segs.upper_bound(p);
if(it != segs.begin()) it = prev(it);
pair<int,int> p1 = *it;
// divide p1 in two
int len = p1.second - p1.first +1;
ans -= (len*(len+1))/2;
pair<int,int> seg1; pair<int,int> seg2;
seg1 = {p1.first, x-1}; seg2 = {x+1, p1.second};
// cerr<<"X: "<<x<<" J: "<<j<<" P1 "<<p1.first<<" "<<p1.second<<" SEG1 "<<seg1.first<<" "<<seg1.second<<" SEG2 "<<seg2.first<<" "<<seg2.second<<endl;
if(seg1.second >= seg1.first) segs.insert(seg1), ans+= calc(seg1);
if(seg2.second >= seg2.first) segs.insert(seg2), ans+= calc(seg2);
segs.erase(p1);
// cerr<<"SEGS: ";
// for(auto z : segs) cout<<z.first<<" "<<z.second<<" "; cout<<endl;
}
else{
q[i] = ans;
}
}
}
for(int i : q) cout<<i<<endl;
}
