数列 \(A\) を前から順番に見ていって，ある値 \(x\) が最後に現れた位置，すなわち \(A_j=x\) となる最大の \(j\) を配列 \(\mathrm{last}\) に格納していくことを考えます．すると，以下のようなアルゴリズムが考えられます．

• 配列 \(\mathrm{last}\) の要素を \(-1\) で初期化する
• \(i=1,2,\dots,N\) について，以下を行う
  • \(B_i \leftarrow \mathrm{last}[A_i]\) とする
  • \(\mathrm{last}[A_i] \leftarrow i\) とする

このアルゴリズムの問題点は，\(A_i\) は最大で \(10^9\) の値を取るため，配列 \(\mathrm{last}\) の長さを \(10^9\) だけ確保しなければいけない点です．このような大きな配列はメモリに入りません．

このような場合に便利なのが 連想配列 です．連想配列は，通常の配列と同様に，与えられた添字に対してそれに紐づいている値を返すデータ構造ですが，連想配列では添字の集合が可変なので，必要なところだけ記憶しておくことができます．今回の問題では，\(A_i\) は最大で \(10^9\) ですが，実際に添字として現れるのは，\(A\) に現れる値（たかだか \(N\leq 2\times 10^5\) 個）のみなので，連想配列を用いることで必要なメモリを減らすことができます．

連想配列は，多くの言語で標準機能として提供されています．C++では map や unordered_map，Python では dict として利用することができます．

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))
last = {}
B = [-1] * N
for i in range(N):
    if A[i] in last:
        B[i] = last[A[i]]
    last[A[i]] = i + 1
print(*B)

実装例 (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (auto& x : A) cin >> x;
    map<int, int> last;
    vector<int> B(N, -1);
    for (int i = 0; i < N; ++i) {
        if (last.contains(A[i])) {
            B[i] = last[A[i]];
        }
        last[A[i]] = i + 1;
    }
    for (int i = 0; i < N; ++i) {
        cout << B[i] << (i < N - 1 ? " " : "\n");
    }
}