Дима увлекается последовательностями чисел. Сейчас у него есть последовательность a1, a2, ..., an, состоящая из n целых положительных чисел. А так же у Димы есть функция f(x), которую можно определить следующим рекуррентным соотношением:
- f(0) = 0;
- f(2·x) = f(x);
- f(2·x + 1) = f(x) + 1.
Диму заинтересовал вопрос: сколько существует пар индексов (i, j) (1 ≤ i < j ≤ n), таких что f(ai) = f(aj). Помогите ему, посчитайте, сколько таких пар.
Выходные данные
В единственную строку выведите ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на C++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
В первом примере любая пара (i, j) подойдет, поэтому ответ — 3.
Во втором примере подходит только пара (1, 2).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 4
|
3
|
|
2
|
3
5 3 1
|
1
|