题目描述

给定一个严格递增的整数序列：

$$0\le a_1<a_2<\cdots<a_N\le 10^{18}。$$

你的任务是求出最大的相邻差值：

$$\max_{1\le i<N}(a_{i+1}-a_i)。$$

但是，你不能直接访问整个序列。你只能通过评测程序提供的函数 MinMax 进行询问。

提交要求

你需要提交一个 C++ 源文件，实现如下函数：

long long findGap(int T, int N);

你的程序需要包含头文件：

#include "gap.h"

其中：

• T 表示当前子任务编号，只可能为 1 或 2；
• N 表示序列长度。

你的提交文件：

• 不要定义 main 函数；
• 不要从标准输入读入；
• 不要向标准输出输出；
• 只需要实现 findGap 以及你需要的辅助函数。

询问函数

你可以调用如下函数：

void MinMax(long long s, long long t, long long *mn, long long *mx);

调用：

long long mn, mx;
MinMax(s, t, &mn, &mx);

评测程序会在隐藏序列中查找所有位于区间 $[s,t]$ 内的数。

• 如果存在这样的数，mn 会被赋值为其中的最小值，mx 会被赋值为其中的最大值；
• 如果不存在这样的数，mn 和 mx 都会被赋值为 -1。

调用时必须满足：

$$s\le t。$$

否则评测结果为 Wrong Answer。

输入格式

选手程序不需要直接读入输入。

评测程序内部会读入测试数据，并调用你的 findGap(T,N)。

测试数据格式为：

第一行两个整数 $T,N$。

第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$，表示隐藏序列。

输出格式

选手程序不需要直接输出。

你只需要在 findGap 中返回最大相邻差值。

数据范围

$$2\le N\le 100000$$ $$0\le a_1<a_2<\cdots<a_N\le 10^{18}$$ $$T\in\{1,2\}$$

计费方式与限制

记询问代价为 $M$。

子任务 1

每调用一次 MinMax，$M$ 增加 $1$。

要求：

$$M\le \left\lceil\frac N2\right\rceil = \frac{N+1}{2}。$$

子任务 2

若某次调用 MinMax(s,t) 时，隐藏序列中有 $k$ 个数位于 $[s,t]$ 内，则 $M$ 增加：

$$k+1。$$

要求：

$$M\le 3N。$$

原题对子任务 2 的超限询问有部分分公式。为了适配 Hydro OJ 的普通评测，本版本将其改为硬限制：答案正确且询问代价满足限制才能通过对应测试点。

子任务

子任务	分值	测试点	限制
1	30	1--32	$T=1$，$M\le (N+1)/2$
2	70	33--64	$T=2$，$M\le 3N$

本地测试

• gap.h
• Lgrader.cpp

本地测试时，把你的 gap.cpp 与这两个文件放在同一目录下，然后编译：

g++ -std=c++17 -O2 gap.cpp Lgrader.cpp -o gap

然后使用测试数据作为标准输入运行。

注意：本地 Lgrader.cpp 只用于帮助调试，正式评测使用 Hydro 配置包中的 grader.cpp。

@下发文件

样例说明

由于本题采用函数式提交形式，选手程序不直接读写标准输入输出，故不提供传统样例输入输出。