There are n sticks, the i-th of which has length ai
. Alex wants to assemble from them as many
parallelograms as possible simultaneously, with each stick used at most in one parallelogram. What
maximal number of parallelograms is it possible to assemble?
Input
The first line contains a single integer n (1 ≤ n ≤ 200000) — the number of sticks.
The second line contains n integers ai (1 ≤ ai ≤ 200000) — the lengths of sticks.
Output
Output a single integer — the maximal number of parallelograms that is possible to assemble.
Examples
standard input standard output
4
1 2 1 2
1
12
1 3 5 7 1 3 5 7 1 3 5 7
2
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 500005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool prime(int x) {
if (x == 0 || x == 1)return false;
for (int i = 2; i <= sqrt(x); i++) {
if (x%i == 0)return false;
}
return true;
}
int a[maxn];
map<int, int>mp;
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
int i, j;
for (i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]]++;
}
int cnt = 0;
for (i = 1; i <=200000; i++) {
if (mp[i] % 2 == 1) {
mp[i]--;
}
}
for (i = 1; i <=200000; i++) {
if (mp[i] >= 2 && mp[i] % 2 == 0) {
cnt += (mp[i] / 2);
}
}
if (cnt % 2 == 1) {
cout << cnt / 2 << endl;
}
else {
cout << cnt / 2 << endl;
}
}