You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 1.0 秒

空间限制： 512 MB

虽然但是，本题时空限制没什么用，且本题只支持 C++ 完成。

题目描述

已知一个长度为 $n$ 的正整数序列 $a_0,...,a_{n-1}$，且存在一个整数 $k\in[0,n)$，使得 $a_0,...,a_{k-1}$ 严格单调递增，$a_{k},...,a_{n-1}$ 严格单调递减，$a_k$ 为该序列当中的最大值。

你需要设计一个算法找出对应的 $k$。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 peak.h。

你需要实现一个函数 int findPeak(int)，传入参数为 $n$，表示正整数序列的长度；返回值见题目描述，为对应的单峰位置 $k$。

你可以调用函数 int get(int)，参数是一个介于 $0$ 到 $n-1$ 之间的整数 $x$，返回值为 $a_x$。你无法得知具体的正整数序列，只能使用 get 函数获取。当 get 调用次数超过 $100$，或者传入参数越界，则会报 Runtime Error。

以下我们给出一个代码提交实例（会固定返回答案 114514，仅作为示例，不保证能得分）：

#include "peak.h"
int findPeak(int n)
{
    return 114514;
}

你不需要，也不应该，实现主函数。

子任务

对于所有数据，保证 $1\le n\le 10^6,~1\le a_i\le 2\times 10^9$。

提示

我们需要一个 $O(\log n)$ 的算法解决本问题。此外，你的代码需要能够处理特殊的边界情况。