#include<bits/stdc++.h> #include"gap.h" using namespace std; void MinMax(long long s, long long t, long long *mn, long long *mx); #define ll long long long long findGap(int t, int n) { if(t==1) { ll a[n]; ll x=0, y=1e18; for(int i=0,j=n-1; i<=j && i<n && j>=0; i++, j--) { ll mn,mx; MinMax(x,y,&mn,&mx); a[i]=mn,a[j]=mx; x=mn+1,y=mx-1; } ll ans=0; for(int i=0; i<n-1; i++) ans=max(a[i+1]-a[i], ans); return ans; } else { ll x,y; MinMax(0, 1e18, &x, &y); ll mx=y; ll ans=(y-x)/(n-1); ll i=x+1, j,l=x; for(;;) { MinMax(i, i+ans-1, &x, &y); if(x!=-1) { if(x-l>ans) { ans=x-l; i=x+1; l=x; } else { l=y; i=y+1; } } else { i=i+ans; } if(i>1e18 || y==mx) break; } return ans; } } // #include <stdio.h> // #include <stdlib.h> // static void my_assert(int k){ if (!k) exit(1); } // static int subtask_num, N; // static long long A[100001]; // static long long call_count; // long long findGap(int, int); // void MinMax(long long s, long long t, long long *mn, long long *mx) // { // int lo = 1, hi = N, left = N+1, right = 0; // my_assert(s <= t && mn != NULL && mx != NULL); // while (lo <= hi){ // int mid = (lo+hi)>>1; // if (A[mid] >= s) hi = mid - 1, left = mid; // else lo = mid + 1; // } // lo = 1, hi = N; // while (lo <= hi){ // int mid = (lo+hi)>>1; // if (A[mid] <= t) lo = mid + 1, right = mid; // else hi = mid - 1; // } // if (left > right) *mn = *mx = -1; // else{ // *mn = A[left]; // *mx = A[right]; // } // if (subtask_num == 1) call_count++; // else if (subtask_num == 2) call_count += right-left+2; // } // int main() // { // FILE *in = stdin, *out = stdout; // my_assert(2 == fscanf(in, "%d%d", &subtask_num, &N)); // my_assert(1 <= subtask_num && subtask_num <= 2); // my_assert(2 <= N && N <= 100000); // for (int i=1;i<=N;i++) my_assert(1 == fscanf(in, "%lld", A+i)); // for (int i=1;i<N;i++) my_assert(A[i] < A[i+1]); // fprintf(out, "%lld\n", findGap(subtask_num, N)); // fprintf(out, "%lld\n", call_count); // }