#11389. 山峰数组的顶部

内存限制:256 MiB 时间限制:20 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

符合下列属性的数组 a 称为 山峰数组(山脉数组) :

  • a 的元素个数 n >= 3
  • 存在 i(0 < i < n - 1)使得:
    • a[0] < a[1] < ... a[i-1] < a[i]
    • a[i] > a[i+1] > ... > a[n - 1]

给定由整数组成的山峰数组 a ,返回任何满足 a[0] < a[1] < ... a[i - 1] < a[i] > a[i + 1] > ... > a[n - 1] 的下标 i ,即山峰顶部。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

输入格式

第一行,n

第二行,数组 a 的 n 个元素

输出格式

山峰顶部

样例

示例 1:

输入:

3
0 1 0

输出:

1

示例 2:

输入:

5
1 3 5 4 2

输出:

2

示例 3:

输入:

4
0 10 5 2

输出:

1

示例 4:

输入:

4
3 4 5 1

输出:

2

示例 5:

输入:

10
24 69 100 99 79 78 67 36 26 19

输出:

2

数据范围与提示

3 <= n <= 10^4

0 <= a[i] <= 10^6

题目数据保证 arr 是一个山脉数组