#2348. 重排

重排

题目描述

t\red{t}每次给定一个长度为n\red{n}的序列a\red{a}。定义数对(i,j)\red{(i,j)}是优美的当且仅当1<=i<j<=n,gcd(ai,2×aj)>1\red{1<=i <j<=n,gcd(a_i,2\times a_j)>1} 。请求出将原序列重排后可以产生的优美数对个数的最大值。

输入格式

第一行一个整数n\red{n,}表示序列长度。

接下来一行n\red{n}个整数ai\red{a_i,}表示序列。

输出格式

输出一行一个整数,表示答案。

样例

输入样例1

4
3 6 5 3

输出样例1

4

输入样例2

5
1 4 2 4 1

输出样例2

9

提示

对于50%\red{50\%}的数据,有1<=n<=20\red{1<=n<=20}

对于100%\red{100\%}的数据,有1<=n<=2000,1<=ai<=105\red{1<=n<=2000,1<=a_i<=10^5}