O(N)이 돌아가기는 하지만 대부분의 경우 0.4초대에 푼 점과 구현 방식에 따라서 시간 초과가 나기도 하는 등 0.5초 제한은 O(N) 풀이에 대해서 상당히 애매한 거 같네요.

O(N)을 허용하지 않는다면 0.1초로 줄이거나 허용한다면 1초 이상으로 늘리는 것이 좋을 것 같아요.