31503번 - DP (Large)

문제

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

DP는 DYNAMIC Porani의 약자이다.

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

방학을 맞은 포라니는 알고리즘 능력 향상을 위해 선배로부터 추천 문제 셋을 받았다. 나태한 포라니는 모든 문제를 풀고 싶지 않다. 만약 선배로부터 어떤 문제를 풀라는 지시를 받았을 때, 그 문제를 포함하여 DYNAMIC하게 문제를 풀었을 경우 몇 문제를 풀어야 하는지 알려주자.

입력

첫 번째 줄에 문제의 수 $N(1 \le N \le 300,000円)$과 쿼리의 수 $Q(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$번째 선배의 지시에 따라 풀어야 하는 문제 수를 순서대로 출력한다.

제한

힌트