DP (Large)

This problem differs from DP (Small) in the limits on the number of problems, the number of queries, and the difficulty range.

DP is short for DYNAMIC Porani.

A DYNAMIC Porani likes to solve the problems she can solve in a DYNAMIC way. A DYNAMIC solution means solving as many problems as possible so that both the problem number and the difficulty strictly increase.

Over break, Porani received a set of recommended problems from her senior to improve her algorithm skills. Being lazy, she does not want to solve every problem. When a senior tells her to solve a certain problem, tell her how many problems she must solve in a DYNAMIC way that includes that problem.

The first line contains two integers $N$ and $Q$ ($1 \le N \le 300\,000$, $1 \le Q \le N$), separated by a space.

The second line contains non-negative integers $D_i$ ($1 \le i \le N$; $0 \le D_i \le 3 \times 10^8$), the difficulty of each problem in order of problem number, separated by spaces. Problem numbers are consecutive positive integers starting from $1$.

From the third line, $Q$ lines follow, each containing a problem number $A_i$ ($1 \le i \le Q$; $1 \le A_i \le N$) that a senior asked Porani to solve. The problem numbers in the queries are distinct.

Print $Q$ lines. On line $i$, print the number of problems Porani must solve for the $i$-th senior instruction, in order.