정올시는 왼쪽에서 오른쪽으로 쭉 뻗은 직선 도로를 따라 건설된 도시이다.

도로는 수직선으로 표현되며 그 위에 N개의 건물이 있다.

왼쪽부터 i번째 건물은 도로의 [L_i, R_i] 구간에 지어져 있으며 서로 겹치지 않는다.

정올시의 여름은 매우 덥다.

정올시의 시장 서현이는 시민들을 위해 햇빛을 피할 수 있게 공사를 준비 중이다.

당연하지만 건물 안에서는 햇빛을 피할 수 있다.

또 건물 끝에 처마를 달면 그 부분 밑에서는 햇빛을 피할 수 있다.

서현이는 총 Q개의 계획을 해보고 있다.

서현이의 i번째 계획은 S_i번째 건물부터 E_i번째 건물까지 햇빛을 전혀 받지 않고 이동할 수 있게 처마를 다는 계획이다.

다시 말해, 두 건물 사이의 어떤 점에서도 햇빛을 받지 않도록 처마를 달아야 한다.

하지만 처마를 아무렇게나 달 수는 없다.

한 건물에 달려있는 처마가 너무 무거우면 그만큼 붕괴 위험이 늘어난다.

따라서 서현이는 각 계획을 실행하면서 한 건물에 달아야 하는 처마 길이 합의 최댓값을 최소화 하고 싶다.

한 번 서현이를 도와 계획의 최솟값을 구해보자!

처마 timer 2s memory 1024MB

처마 2s 1024MB