投放探针

归途计算完了，但Zero的核心还需要探测——用探针，投放进未知的区域。

"探针？"CC问。

"对。"你说，"给定$n$个点，每个点有一个高度。我们要找最高的点。"

"最高的？"

"对。"你说，"但不知道所有点的高度，只能一个一个探测。"

"咋探测？"

"三分。"你说，"如果函数是单峰的（先增后减），可以在中间取两个点，比较大小，然后缩小区间。"

"单峰？"

"对。"你说，"只有一个最高点，两边都低。"

"第47个点。"你说，"高度47——可能不是最高，但值得探测。"

"探测完呢？"

"比较。"你说，"如果左边高，往左缩；如果右边高，往右缩。"

"多快？"

"$O(\log n)$。"你说，"每次缩小区间的$1/3$。"

"准吗？"

"对连续函数准。"你说，"对离散点，近似。"

CC看着那些点——像星星，像山峰，像某种高低不平的地形。

"最高的在哪？"她问。

"不知道。"你说，"但探针会帮我们找到。"

"探针是啥？"

"就是计算。"你说，"算几个点的高度，比较，再算。"

"像摸黑走路。"

"对。"你说，"像摸黑走路——一步一步，感受高低。"

Echo把探针的轨迹投射出来——弯弯曲曲，但一直向高处移动。

"以前我不敢探测。"她说，"怕落空。"

"现在呢？"

"现在投了。"她说，"因为你们知道怎么找。"

题目描述

给定单峰函数$f(x)$，求其在区间$[l,r]$上的最大值点。

输入格式

单峰函数由$n$个离散点给出。第一行$n$，接下来$n$行每行$x_i$和$y_i$。

输出格式

最大值点的坐标。

输入样例

5

输出样例

0

提示

• 三分法：取$m_1=l+(r-l)/3$，$m_2=r-(r-l)/3$。
• 比较$f(m_1)$和$f(m_2)$，缩小区间。
• 时间复杂度$O(\log n)$。