Vector magic: removing duplicates while preserving order

C++ Hard vectors

Task «Vector magic: removing duplicates while preserving order»

Given a vector of integers. It is necessary to remove all duplicates from it, leaving only the first occurrence of each element, while the order of the elements must be preserved. Implement a function that takes a vector and returns a new vector without duplicates. Using std::set or std::unordered_set is prohibited. Input data: first an integer N (1 ≤ N ≤ 10^5) — the number of elements, then N integers, each with an absolute value not exceeding 10^9. Output the resulting vector separated by spaces.

Input Format

First line: an integer N (1 ≤ N ≤ 10^5). Second line: N integers separated by spaces.

Output Format

One line: elements of the resulting vector, separated by spaces.

Examples

Example 1

INPUT

5
1 2 3 2 1

OUTPUT

1 2 3

Example 2

INPUT

6
4 5 6 5 4 3

OUTPUT

4 5 6 3

Example 3

INPUT

5
1 2 3 4 5

OUTPUT

1 2 3 4 5

Example 4

INPUT

4
7 7 7 7

OUTPUT

7

Example 5

INPUT

8
2 5 2 8 5 6 8 8

OUTPUT

2 5 8 6

main.cpp