정올 왕국은 평면 좌표 위에 존재한다.
N개의 마을이 있고, 각 마을에는 1번부터 N번까지 번호가 붙어 있다.
마을 i는 좌표 (i, 0)에 있는 점으로 간주한다.

지금 정올 왕국에서는 이 마을들을 연결하는 통신 회선을 정비하려 한다.
장애에 대비하여 통신 회선은 두 개의 네트워크로 나눠 관리하고 있다.

아래 그림은 문제의 두 예제에 대한 그림이다.
회색 원은 네트워크 1의 허브, 검은색 원은 네트워크 2의 허브, 흰색 원은 마을을 나타낸다.

두 지점이 통신 가능하다는 것은, 회선을 따라 이동하며 한 지점에서 다른 지점으로 갈 수 있음을 의미한다.
문제에서 주어진 조건 하에, 네트워크 1만으로도 임의의 두 마을 및 허브가 모두 통신 가능하며, 네트워크 2만으로도 마찬가지이다.

이 계획에 대한 안전성을 평가하기 위해, 두 정수 A (A ≥ 0), B (B ≤ 0)를 받아서
y좌표가 A보다 큰 모든 허브와 y좌표가 B보다 작은 모든 허브를 ‘파괴’한다고 가정하자.

허브가 파괴되면 그 허브를 경유하는 통신이 모두 불가능해진다.

마을 및 두 계통의 정보가 주어지고, Q개의 쿼리가 주어진다.
각 쿼리 i에는 정수 A_i가 주어졌을 때, "y > A_i인 모든 허브와 y < B인 모든 허브를 파괴해도
모든 마을 사이의 통신이 유지되는” 가장 큰 정수 B_i (B_i ≤ 0)를 구하여라.

네트워크 정비 timer 2s memory 1024MB

네트워크 정비 2s 1024MB