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점을 받는다.

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

차이 timer 2s memory 512MB

차이 2s 512MB