AtCoder Beginner Contest 159 D 問題

Question

前提・実現したいこと

AtCoder Beginner Contest 159 D 問題をPythonで解いているのですが，TLEになってしまいます。
このコードはforループが２つ，どちらもO(n)なので，全体としてもO(n)のはずなのですが，なぜTLEになってしまうのでしょうか。
見たところ，.countが負荷が大きいコマンドなのでしょうか。
他の方の解答を見て，この問題の解法は分かったのですが，なぜ自分のコードでTLEになってしまうのかが良く分かりません。

発生している問題・エラーメッセージ

O(n)のはずなのにTLEを起こしてしまう。
そもそもO(n)でないのか，何かのコマンドが負荷が大きいものなのか，原因を教えてください。

該当のソースコード

n = int(input())
a = list(map(int, input().split()))

def cmb(n):
    return int(n*(n-1)/2)

goukei = 0
count = 0

for i in range(n):
    if a[i] in a[:i]:
        continue
    else:
        count = a.count(a[i])
        goukei += cmb(count)

for i in range(n):
    print(goukei - (a.count(a[i]) - 1))

Answer 1

list.countは線型探索を行います。
O(n)の処理がループ内に入っているので、これはO(n^2)ですね。

---

また、 a[i] in a[:i] も定数時間では実行できません。