Bombs

You are given a permutation, $p_1, p_2, \ldots, p_n$.

Imagine that some positions of the permutation contain bombs, such that there exists at least one position without a bomb.

For some fixed configuration of bombs, consider the following process. Initially, there is an empty set, $A$.

For each $i$ from $1$ to $n$:

• Add $p_i$ to $A$.
• If the $i$-th position contains a bomb, remove the largest element in $A$.

After the process is completed, $A$ will be non-empty. The cost of the configuration of bombs equals the largest element in $A$.

You are given another permutation, $q_1, q_2, \ldots, q_n$.

For each $1 \leq i \leq n$, find the cost of a configuration of bombs such that there exists a bomb in positions $q_1, q_2, \ldots, q_{i-1}$.

For example, for $i=1$, you need to find the cost of a configuration without bombs, and for $i=n$, you need to find the cost of a configuration with bombs in positions $q_1, q_2, \ldots, q_{n-1}$.Input

The first line contains a single integer, $n$ ($2 \leq n \leq 300\,000$).

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n)$.

The third line contains $n$ distinct integers $q_1, q_2, \ldots, q_n$ ($1 \leq q_i \leq n)$.Output

Print $n$ space-separated integers, such that the $i$-th of them equals the cost of a configuration of bombs in positions $q_1, q_2, \ldots, q_{i-1}$.Examplesinput

3
3 2 1
1 2 3

output

3 2 1 

input

6
2 3 6 1 5 4
5 2 1 4 6 3

output

6 5 5 5 4 1 

Note

In the first test:

• If there are no bombs, $A$ is equal to $\{1, 2, 3\}$ at the end of the process, so the cost of the configuration is $3$.
• If there is one bomb in position $1$, $A$ is equal to $\{1, 2\}$ at the end of the process, so the cost of the configuration is $2$;
• If there are two bombs in positions $1$ and $2$, $A$ is equal to $\{1\}$ at the end of the process, so the cost of the configuration is $1$.

In the second test:

Let’s consider the process for $i = 4$. There are three bombs on positions $q_1 = 5$, $q_2 = 2$, and $q_3 = 1$.

At the beginning, $A = \{\}$.

• Operation $1$: Add $p_1 = 2$ to $A$, so $A$ is equal to $\{2\}$. There exists a bomb in position $1$, so we should delete the largest element from $A$. $A$ is equal to $\{\}$.
• Operation $2$: Add $p_2 = 3$ to $A$, so $A$ is equal to $\{3\}$. There exists a bomb in position $2$, so we should delete the largest element from $A$. $A$ is equal to $\{\}$.
• Operation $3$: Add $p_3 = 6$ to $A$, so $A$ is equal to $\{6\}$. There is no bomb in position $3$, so we do nothing.
• Operation $4$: Add $p_4 = 1$ to $A$, so $A$ is equal to $\{1, 6\}$. There is no bomb in position $4$, so we do nothing.
• Operation $5$: Add $p_5 = 5$ to $A$, so $A$ is equal to $\{1, 5, 6\}$. There exists a bomb in position $5$, so we delete the largest element from $A$. Now, $A$ is equal to $\{1, 5\}$.
• Operation $6$: Add $p_6 = 4$ to $A$, so $A$ is equal to $\{1, 4, 5\}$. There is no bomb in position $6$, so we do nothing.

In the end, we have $A = \{1, 4, 5\}$, so the cost of the configuration is equal to $5$.

Solution:

#include <bits/stdc++.h>

using namespace std;

class segtree {
public:
struct node {
int add = 0;
int mn = 0;

void apply(int l, int r, int v) {
mn += v;
add += v;
}
};

node unite(const node &a, const node &b) const {
node res;
res.mn = min(a.mn, b.mn);
return res;
}

inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}

template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}

int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}

int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}

template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}

node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
vector<int> p(n);
vector<int> pos(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
--p[i];
pos[p[i]] = i;
}
vector<int> q(n);
for (int i = 0; i < n; i++) {
    cin >> q[i];
--q[i];
}
segtree st(n);
st.modify(pos[n - 1], n - 1, 1);
int ans = n - 1;
for (int i = 0; i < n; i++) {
    if (i > 0) {
cout << " ";
    }
    cout << ans + 1;
    if (i == n - 1) {
      break;
    }
    st.modify(q[i], n - 1, -1);
    while (true) {
      int mn = min(0, st.get(0, n - 1).mn);
      int val = st.get(n - 1, n - 1).mn;
      if (val == mn) {
        assert(ans > 0);
--ans;
st.modify(pos[ans], n - 1, 1);
} else {
break;
}
}
}
cout << '\n';
  return 0;
}