CF 1008C Reorder the Array

You are given an array of integers. Vasya can permute (change order) its integers. He wants to do it so that as many as possible integers will become on a place where a smaller integer used to stand. Help Vasya find the maximal number of such integers.

For instance, if we are given an array [10,20,30,40][10,20,30,40], we can permute it so that it becomes [20,40,10,30][20,40,10,30]. Then on the first and the second positions the integers became larger (20>1020>10, 40>2040>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals 22. Read the note for the first example, there is one more demonstrative test case.

Help Vasya to permute integers in such way that the number of positions in a new array, where integers are greater than in the original one, is maximal.

Input

The first line contains a single integer nn (1≤n≤1051≤n≤105) — the length of the array.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.

Output

Print a single integer — the maximal number of the array's elements which after a permutation will stand on the position where a smaller element stood in the initial array.

Examples

Input

7
10 1 1 1 5 5 3

Output

Input

5
1 1 1 1 1

Output

Note

In the first sample, one of the best permutations is [1,5,5,3,10,1,1][1,5,5,3,10,1,1]. On the positions from second to fifth the elements became larger, so the answer for this permutation is 4.

In the second sample, there is no way to increase any element with a permutation, so the answer is 0.

给你一段序列，经过重新排序后，问最多有几个位置上的数比原位置上的数大了。

类似与田忌赛马，但是我并不会操作。

原理是这样的：

　　假设给定的序列是 1 1 2 3 5 5 5 7

　　那么，符合题意的方法是，抽出两个子序列：1 2 3 5 7 和 1 5 ；或者是 1 3 5 7 和 1 2 5 。

　　即找长串，找若干条，直到所给序列中的数都被选过，或无法再选。

方法有了，但是暴力实现的话会超时或者RT，不知道怎么实现，直到发现了网友们的一个极其巧妙的解法，但是那种算法的原理不太理解。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<deque>

 #include<map>

 #include<iostream>

 using namespace std;

 typedef long long  LL;

 const double pi=acos(-1.0);

 const double e=exp();

 const int N = ;

 int con[];

 int num[];

 bool cmp(int a,int b)

 {

     return a<b;

 }

 int main()

 {

     int n,i,p,j;

     int flag,ans=;

     scanf("%d",&n);

     for(i=;i<=n;i++)

     {

         scanf("%d",&con[i]);

     }

     sort(con+,con+n+,cmp);

     int head=;

     for(i=;i<=n;i++)              //巧妙的方法开始了

     {

         if(con[i]>con[head])

         {

             head++;

             ans++;

         }

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

CF 1008C Reorder the Array

最新文章

热门文章