Solution

“Day \(i\) is a new-record day” means \(A_i\) is greater than all of \(A_1, A_2, \ldots, A_{i-1}\), i.e., \(A_i > \max(A_1, \ldots, A_{i-1})\).

So we scan the days in order while keeping the maximum snowfall seen so far in a variable mx. If \(A_i > \mathrm{mx}\), day \(i\) is a new-record day: output o and update mx to \(A_i\). Otherwise output x.

Initializing \(\mathrm{mx} = -1\) guarantees that day 1 is always a new-record day, since \(A_1 \geq 0 > \mathrm{mx}\), which naturally satisfies the statement’s requirement.

Pseudocode

mx = -1
for i = 1..N:
    read A_i
    if A_i > mx:
        output 'o'; mx = A_i
    else:
        output 'x'

Proof of Correctness

Invariant: just before processing day \(i\), \(\mathrm{mx} = \max(A_1, \ldots, A_{i-1})\) (for \(i = 1\), \(\mathrm{mx} = -1\) acts as the maximum of the empty set).

• Base: at \(i = 1\), \(\mathrm{mx} = -1\). Since \(A_1 \geq 0\), we have \(A_1 > \mathrm{mx}\), so day 1 always produces o, satisfying “day 1 is always a new-record day.”
• Step: if \(A_i > \mathrm{mx}\) on day \(i\), we output o and set \(\mathrm{mx} \leftarrow A_i\). By the invariant, \(\mathrm{mx}\) equals the maximum of \(A_1, \ldots, A_{i-1}\), so \(A_i > \mathrm{mx}\) is equivalent to “\(A_i\) is greater than every previous day’s snowfall” — the o decision is correct. After the update, \(\mathrm{mx} = \max(A_1, \ldots, A_i)\). If \(A_i \leq \mathrm{mx}\), we output x and \(\mathrm{mx}\) stays equal to \(\max(A_1, \ldots, A_i)\), preserving the invariant.

Hence the character produced for every \(i\) is correct, and the resulting string is exactly the required answer.

Complexity

• Time: \(O(N)\)
• Space: \(O(1)\) auxiliary if input is consumed one value at a time (excluding the output string). The Python implementation reads all input at once, using \(O(N)\) space, which is fine since \(N \leq 100\).

Tie-breaking

The condition requires \(A_i\) to be greater than all previous days’ values, so equaling the past maximum does not count as a new record and yields x. Therefore the comparison must use a strict inequality >.