25925번 - 안아줘요

문제

날다람쥐 한 마리가 자유 낙하를 하려고 한다.

$N$개의 휴식점이 주어지고, 각각의 휴식점의 좌표 $X_i, Y_i$가 주어진다. 가장 많은 수의 휴식점을 지나가는 것이 날다람쥐의 목표이다.

안아줘요 날다람쥐는 언제나 안아줘요 포즈를 취하고 있기 때문에 공기 저항을 크게 받아 좌우 방향의 이동보다 빠르게 낙하할 수는 없다.

즉, $|Y_i - Y_j| ≤ |X_i - X_j|$이고 $Y_i > Y_j$인 경우에만 $i$번 휴식점에서 $j$번 휴식점으로 이동할 수 있다.

여러 낙하 경로 중에, 가장 많은 휴식점을 지날 수 있는 경로를 선택하여 낙하하려고 한다.

$Q$개의 출발 휴식점 번호가 주어질 때, 해당 휴식점에서 출발해서 지날 수 있는 휴식점의 수를 날다람쥐에게 알려주자.

입력

입력은 아래와 같이 주어진다.

출력

출발 휴식점에서 경유할 수 있는 최대 휴식점의 개수를 한 줄에 하나씩 출력한다. 출발 휴식점과 도착 휴식점도 출력하는 숫자에 포함한다.

제한

• 1ドル \leq N,Q \leq 500,000円$
• 0ドル ≤ X_i, Y_i ≤ 10^9$
• $i \neq j $ $\Rightarrow$ $Y_i \neq Y_j$
• 1ドル \leq q_i \leq N$

힌트