MaxCounters Codility Challenge

Question

I've been doing some Codility challenges lately and the MaxCounters challenge got me stumped:

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) — counter X is increased by 1,
• max counter — all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

• if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
• if A[K] = N + 1 then operation K is max counter.

[...] The goal is to calculate the value of every counter after all operations.

Below is my solution in Python. I can't reach 100% on it even though I am pretty confident it is an O(n+m) complexity solution. Codility fails it and says its an O(n*m) complexity solution.

def solution(N, A):
    counter = [0] * N
    max_val = 0

    for v in A:

        if v <= N and v >= 1:
            if counter[v-1] < max_val+1:
                counter[v-1] = max_val+1
            else:
                counter[v-1] += 1
        else:
            max_val = max(counter)

    for i in range(len(counter)):
        if counter[i] < max_val:
            counter[i] = max_val

    return counter

Answer 1

A couple of hints, to avoid spoiling the problem.

Hint 1

What would happen if every entry in A were N + 1?

Hint 2

What is the complexity of max(counter)?