PostgreSQL NOT IN array slow query

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?

I have solved thanks to Jeff Janes on the pgsql-performance mailing list:

The GIN index was not used by PostgreSQL for the "NOT" operation. Creating a Btree index on the whole array solved the problem, allowing an index only scan. Now the query takes only a few milliseconds instead of minutes.

StackExchange Database Administrators Q#253084, answer score: 4