#P1960. [Baltic2010]Bins

    ID: 982 传统题 1000ms 512MiB 尝试: 77 已通过: 37 难度: 4 上传者: 标签>CF1600普及+/提高-暴力枚举极端元素优先处理交换论证增量维护Day2

[Baltic2010]Bins

[BalticOI 2010 Day2] Matching Bins

题目描述

给定一行 NN 个整数 A1,A2,…,ANA_1,A_2,\dots,A_N。 M=max⁡{A1,A2,…AN}M=\max\{A_1,A_2,\dots A_N\}。

你需要找到一个最大的整数 KK,使得从左至右共 KK 个数都小于接下来的 KK 个数。

输入格式

输入第一行两个整数 M,NM,N,表示数列中的最大数和数的个数。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\dots,A_N。

输出格式

输出一行一个整数,为最大的 KK。

样例 #1

样例输入 #1

5 10
2 2 1 4 3 2 5 4 2 3

样例输出 #1

4

提示

对于 100%100\% 的数据,保证 1≤M≤2×1031\le M\le 2\times 10^3,1≤N≤2×1041\le N\le 2\times 10^4,1≤Ai≤M1\le A_i\le M。


题目译自 BalticOI 2010 Day2 T1 Matching Bins。