DP (Large)

이 문제는 DP (Small)과 문제 수 제한, 질문 수 제한, 문제 난이도 제한이 다른 문제이다.

DP는 DYNAMIC Porani의 약자이다.

DYNAMIC한 포라니는 가능한 문제를 DYNAMIC하게 푸는 것을 좋아한다. DYNAMIC한 문제 풀이란 문제 번호와 난이도가 모두 증가하도록 가능한 한 많은 문제를 푸는 것이다.

방학을 맞은 포라니는 알고리즘 능력을 키우려고 선배로부터 추천 문제 목록을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 선배가 어떤 문제를 풀라고 지시했을 때, 그 문제를 포함해서 DYNAMIC하게 문제를 푼다면 몇 문제를 풀어야 하는지 알려주자.

첫 번째 줄에 문제의 수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다 ($1 \le N \le 300\,000$, $1 \le Q \le N$).

두 번째 줄에 문제의 난이도를 나타내는 음이 아닌 정수 $D_i$ ($1 \le i \le N$; $0 \le D_i \le 3 \times 10^8$)가 문제 번호 순서대로 공백으로 구분되어 주어진다. 문제 번호는 $1$부터 시작하는 연속된 양의 정수이다.

세 번째 줄부터 $Q$개의 줄에 걸쳐 선배가 풀라고 한 문제의 번호 $A_i$ ($1 \le i \le Q$; $1 \le A_i \le N$)가 주어진다. 각 쿼리의 문제 번호는 서로 다르다.

$Q$개의 줄에 걸쳐 $i$번째 줄에 $i$번째 선배의 지시에 따라 풀어야 하는 문제 수를 순서대로 출력한다.