차이 timer 2s memory 512MB

N개의 음이 아닌 정수 a_1, a_2, \cdots, a_N이 있어서 다음 부등식을 만족한다고 한다:

0 \leq a_1 < a_2 < \cdots < a_N \leq 10^{18}.

준혁이는 i가 1부터 N-1까지 변할 때 a_{i+1} - a_i의 최대값을 알고 싶다.

여러분이 준혁이를 도와 이 값을 찾아내주자.

구현할 함수는 long long findGap(long long N)이다 (2 \le N \le 100\,000).

당신은 "gap.h"를 include해야 한다.

당신은 함수 void MinMax(​long long ​s, ​long long ​t, ​long long ​&mn, long long &mx)를 호출할 수 있다.

이 함수는 [s, t] 범위 내의 a_i값들 중 최솟값을 mn에, 최댓값을 mx에 저장한다. 만약 이러한 a_i가 존재하지 않는다면, 둘 다 -1을 저장한다. 함수를 호출할 때 반드시 s \le t를 만족하여야 한다.

[채점 기준]

findGap 함수가 정확한 답을 반환하지 않는다면 0점을 받는다.

정확한 답을 구했다면 아래 방법으로 점수를 매긴다.

• 조건을 만족하는 a_i의 개수를 k라고 하자.

• 모든 MinMax 함수의 호출에 대하여 k+1의 총합을 x라고 하자.

• x \le 3N이면 100점을 받는다.

• 이외의 경우, \frac{60}{\sqrt{\frac{x}{N}+1}-1}로 계산한 점수를 받는다.