ある科学研究の調査で得られた自然数がn個あり、それぞれの数は1500000000（1.5×10⁹）以下である。異なる数の個数は10000個以下である。与えられた自然数それぞれの出現回数をカウントし、自然数の昇順に結果を出力する。

入力形式
最初の行には整数nが与えられる。続くn行には自然数が一つずつ書かれている。

出力形式
異なる数の個数m行が出力される。各行には自然数とその出現回数をスペースで区切って出力する。出力は自然数の昇順にすること。

入力例

8
2
4
2
4
5
100
2
100

出力例

2 3
4 2
5 1
100 2

制約

• 40%のデータ: 1 ≤ n ≤ 1000
• 80%のデータ: 1 ≤ n ≤ 50000
• 100%のデータ: 1 ≤ n ≤ 200000、各数は1500000000以下

この問題ではSTLや関連ライブラリの使用は禁止されている。

解説

問題の規模から、以下の点に注意する必要がある。

1. 各数値が1.5×10⁹以下であるため、バケットソートは使用できない。
2. 100%のデータにおいて、n ≤ 200000、異なる数の個数 ≤ 10000である。このため、O(n²)のアルゴリズムは使用不可。O(n log n)程度までなら許容される。二分探索の利用が想定される。

二分探索を使用する場合、事前に配列をソートしておく必要がある。ここでは挿入ソートを用いることで、要素の追加とソートを同時に処理する。挿入ソートの最悪計算量はO(m²)だが、mは最大10000であり、問題ない。

二分探索の実装において、境界条件を扱いやすくするために、仮想的な境界値を設定する。左端を-1、右端を2×10⁹とする。また、配列のインデックスを2倍にして偶数番地に格納することで、挿入操作を効率的に行う。

実装コード

// 数字出現回数の統計
#include <iostream>
using namespace std;

const int MAX_VAL = 2000000000;
int n, values[20001], counts[20001], input_val, total, pos_index;
int find_position(int val, int left, int right) {
    int mid = (left + right) / 2;
    if (right - left == 2) return mid;
    if (mid % 2) mid--;
    if (val == values[mid]) return mid;
    if (val < values[mid]) return find_position(val, left, mid);
    return find_position(val, mid, right);
}

int main() {
    ios::sync_with_stdio(false);
    values[0] = -1;
    values[2] = MAX_VAL;
    cin >> n;
    
    for (int i = 1; i <= n; i++) {
        cin >> input_val;
        pos_index = find_position(input_val, 0, total + 2);
        if (pos_index % 2) {
            total += 2;
            for (int j = total + 2; j > pos_index + 1; j -= 2) {
                values[j] = values[j - 2];
                counts[j] = counts[j - 2];
            }
            values[pos_index + 1] = input_val;
            counts[pos_index + 1] = 1;
        } else {
            counts[pos_index]++;
        }
    }
    
    for (int i = 2; i <= total; i += 2) {
        cout << values[i] << ' ' << counts[i] << endl;
    }
    return 0;
}