Overview

This problem involves scanning a sequence from left to right, ignoring a value if it’s the same as the last recorded value, and appending it otherwise.
In other words, it can be thought of as a problem of collapsing consecutive identical values into one.

Analysis

The conditions for deciding whether to append to the record list are:

• If the record list is empty, append
• If the current value differs from the last element of the record list, append
• If they are the same, do not append

The key point here is that the comparison should be made only against the last element of the record list, not the entire list.
For example, given

\(A = [1, 1, 2, 2, 2, 3, 1, 1]\)

the process goes as follows:

• Append \(1\) → \([1]\)
• The next \(1\) is the same as the last element, so ignore → \([1]\)
• \(2\) differs from the last element, so append → \([1, 2]\)
• The next \(2, 2\) are ignored → \([1, 2]\)
• Append \(3\) → \([1, 2, 3]\)
• \(1\) differs from the last element \(3\), so append → \([1, 2, 3, 1]\)
• The next \(1\) is ignored

The final answer is

\([1, 2, 3, 1]\)

Key Insight

What we want to remove in this problem is only consecutive duplicates.
For example, in \([1, 2, 1]\), the last \(1\) must not be removed.
It’s important to note that this is not a problem about checking “whether the same value has appeared before in the past.”

Issues with a Naive Approach

For instance, approaches such as:

• Checking the entire record list for duplicates each time
• Removing consecutive sections all at once afterward

may take unnecessarily long.
Since \(N \leq 5 \times 10^5\) is large, we want to process it in \(O(N)\) by examining each element exactly once.

By remembering only the last recorded value, we can process each element in constant time.

Algorithm

The processing follows these steps:

1. Prepare an empty array res
   This will hold the final record list.

2. Use last to keep track of the “last appended value”

3. Scan the sequence from left to right
   For each value x:

   • If res is empty, append x
   • Otherwise, if x != last, append it
   • If x == last, ignore it

4. Output res from the beginning in order

With this method, we only need to check “whether the current value is the same as the most recently adopted value,” making it very simple.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(N\) is large, the code uses sys.stdin.buffer.read() for fast input.

• The comparison with the last element can also be done using res[-1], but in this code, holding last as a separate variable makes it clearer.

• last is updated only when a value is appended.
  This ensures that it always holds a value consistent with the current last element of the record list.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:1 + n]

    res = []
    last = None
    for x in a:
        if not res or x != last:
            res.append(x)
            last = x

    sys.stdout.write('\n'.join(map(str, res)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.