Slow "not in array" operation - Mailing list pgsql-performance

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