「記録リスト」を問題文の指示通りに作成すればよいです。計算量は \(O(N)\) です。

実装例 (C++)

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  vector<int> ans;
  for(int i=0; i<n; i++){
    if(ans.size() == 0 || a[i] != ans.back()){
      ans.push_back(a[i]);
    }
  }

  for(int x: ans){
    cout << x << endl;
  }
}

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))

ans = []
for i in range(N):
  if len(ans) == 0 or A[i] != ans[-1]:
    ans.append(A[i])

for a in ans:
  print(a)