Consider finding the answer in ascending order of \(k\).

When \(k=k_0\), suppose the first three elements when \(A_1\) through \(A_k\) are sorted in descending order are \(x_1,x_2,x_3\). Then, for \(k=k_0+1\), the largest three elements are the largest three among \(x_1,x_2,x_3,A_{k_0+1}\).

Therefore, it is sufficient to scan \(k\) in ascending order, maintain the largest three elements among \(A_1\) through \(A_k\), and retain the three largest elements out of four on each step.

Sample code (Python 3)

n = int(input())
a = list(map(int, input().split()))
s = a[:3]
s.sort(reverse=True)
print(s[2])
for k in range(3, n):
    s.append(a[k])
    s.sort(reverse=True)
    s.pop()
    print(s[2])

Bonus: instead of finding the \(3\)-rd largest, find the \(K\)-th largest. (Worth ABC-D)