#P3322. 朋友圈-T4

    ID: 4704 传统题 1000ms 128MiB 尝试: 15 已通过: 12 难度: 2 上传者: 标签>南海区赛2021南海小学算法前缀和下标计数

朋友圈-T4

题目描述

多多很喜欢发朋友圈,至今他已经发了 NN 条朋友圈,并且他的第 ii 条朋友圈获得了 cic_i 次点赞。多多听说有一个 hh 指数来衡量朋友圈的质量,hh 指数是指有至少 hh 条获得了不少于 hh 次点赞的朋友圈的最大整数 hh

例如,有 44 条朋友圈获得的点赞次数为 (1,100,2,3)(1, 100, 2, 3),则 hh 指数为 22;如果点赞次数为 (1,100,3,3)(1, 100, 3, 3),则 hh 指数为 33

多多想知道自己的 hh 指数是多少。

输入格式

第一行一个整数 NN。 第二行 NN 个整数,第 ii 个整数 cic_i 表示第 ii 条朋友圈获得的点赞次数。

输出格式

输出一个整数,表示多多的 hh 指数。

样例

4
1 100 2 3
2

提示

44 条朋友圈的点赞数分别为 1,100,2,31, 100, 2, 3

  • h=3h=3 时需要至少 33 条点赞数 3\ge 3,符合条件的只有 10010033,共 22 条,不满足;
  • h=2h=2 时需要至少 22 条点赞数 2\ge 2,符合条件的有 100,2,3100, 2, 3,共 33 条,满足; 不存在更大的满足条件的整数,故 hh 指数为 22

数据范围

  • 1N1000001 \le N \le 100000
  • 0ci1000000 \le c_i \le 100000