Slow "not in array" operation

I have a large table with millions of rows. Each row has an array field
"tags". I also have the proper GIN index on tags.

Counting the rows that have a tag is fast (~7s):
SELECT COUNT(*) FROM "subscriptions" WHERE (tags @> ARRAY['t1']::varchar[]);

However counting the rows that don't have a tag is extremely slow (~70s):
SELECT COUNT(*) FROM "subscriptions" WHERE NOT (tags @>
ARRAY['t1']::varchar[]);

I have also tried other variants, but with the same results (~70s):
SELECT COUNT(*) FROM "subscriptions" WHERE NOT ('t1' = ANY (tags));

How can I make the "not in array" operation fast?

Any help would be appreciated, thank you!
Marco Colli

PostgreSQL 11 on Ubuntu 18LTS