问题 4889 --网络热门生物鉴定Ⅲ

4889: 网络热门生物鉴定Ⅲ★★

时间限制: 1 Sec  内存限制: 256 MB
提交: 99  解决: 53
[提交][状态][命题人:]

题目描述

小亮在参观动物园时,正好遇到了熊猫的进食时间。
饲养员准备了 n 份竹子,其中第 i 份竹子的美味度为 a[i] 。熊猫会从前往后依次吃竹子,每当熊猫吃到的竹子比前一个竹子更美味时,它的开心度就加 1 。
为了让熊猫变得更开心,小亮准备将这些竹子重新排序。
问按任意顺序排列这些竹子后,熊猫能获得的最大开心度是多少?即以任意顺序重新排列数组 a[] ,求最多有多少 i (1≤i≤n-1) ,满足 a[i+1]>a[i] 。

输入

第一行包含 1 个整数 n (1≤n≤1000) ,表示竹子数量。
第二行包含 n 个整数 a[1],a[2],...,a[n] (1≤a[i]≤1000),表示每个竹子的美味度。

输出

输出一个整数,表示答案。
样例输入
Copy
5
20 30 10 50 40
样例输出
Copy
4

提示

样例输入2
4
200 100 100 200

样例输出2
2

在第一组样例中,一种最优排列为 10,20,30,40,50 。
在第二组样例中,一种最优排列为 100,200,100,200 。

来源

[提交][状态]