Consider scan the sequence \(A\) from the beginning, while maintaining the last occurring positions of a value \(x\), i.e. the maximum \(j\) with \(A_j=x\), in an array \(\mathrm{last}\). Then we can adopt the following algorithm:

• Initialize the elements of the array \(\mathrm{last}\) with \(-1\).
• For each \(i=1,2,\dots,N\), do the following:
  • Let \(B_i \leftarrow \mathrm{last}[A_i]\).
  • Let \(\mathrm{last}[A_i] \leftarrow i\).

The issue of this problem is that \(A_i\) can be up to \(10^9\), which requires to preserve the array \(\mathrm{last}\) of length \(10^9\); but this does not fit in the memory.

In such cases, it is useful to use an associative array. An array stores values corresponding to certain indices. However, it accepts arbitrary set of indices, memorizing only required part. In our problem, \(A_i\) can be up to \(10^9\), but the actual indices are limited to the values occurring in \(A\) (of at most \(N\leq 2\times 10^5\) kinds), allowing us to reduce the memory required.

Most languages provide associative array as a standard feature. In C++, you can use map or unordered_map; in Python you can use dict.

Sample code (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)

Sample code (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");
    }
}