#11171. 分割数组

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

题目描述

给定一个数组 a ,将其划分为两个连续子数组 left 和 right, 使得:

  • left 中的每个元素都小于或等于 right 中的每个元素。
  • left 和 right 都是非空的。
  • left 的长度要尽可能小。

在完成这样的分组后返回 left 的 长度 。

测试用例可以保证存在这样的划分方法。

输入格式

第一行:正整数n,表示数组a的元素个数

第二行:n个整数

输出格式

分割后,左边数组的长度

样例

输入1:

5
5 0 3 8 6

输出1:

3

解释:

left = [5,0,3],right = [8,6]

输入2:

6
1 1 1 0 6 12

输出2:

4

解释:

left = [1,1,1,0],right = [6,12]

数据范围与提示

2 <= n <= 10^5

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

可以保证至少有一种方法能够按题目所描述的那样对 a 进行划分。