How can I reorder the array in C to achieve a long-tail word?

本文共计833个文字，预计阅读时间需要4分钟。

给定一个整数数组。Vasya 可以重新排列这些整数。他希望尽可能多的整数移动到之前比它们小的整数所在的位置。帮助 Vasya 找到最多可以移动的整数数量。

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][10,20,30,40], we can permute it so that it becomes[20,40,10,30]">[20,40,10,30][20,40,10,30]. Then on the first and the second positions the integers became larger (20>10">20>1020>10,40>20">40>2040>20) and did not on the third and the fourth, so for this permutation, the number that Vasya wants to maximize equals2">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 integern">nn(1≤n≤105">1≤n≤1051≤n≤105)— the length of the array.

The second line containsn">nnintegersa1,a2,…,an">a1,a2,…,ana1,a2,…,an(1≤ai≤109">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

4 Input

5
1 1 1 1 1 Output

0

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][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.

#include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <cstring> #include <cstdlib> #include <map> #include <vector> #include <set> #include <queue> #include <stack> #include <cmath> typedef long long lli; using namespace std; const int mxn = 1e9; multiset<int> v; multiset<int> :: iterator it ; int main() { int n,b,cnt=0; cin>>n; int a[n+5]; for(int i=0; i<n; i++) { cin>>a[i]; v.insert(a[i]); } for(int i=0; i<n; i++) { it = v.lower_bound(a[i]+1); if( it!=v.end() ) { cnt++; v.erase(it); } } cout<<cnt<<endl; return 0; }