We search the five CANDELS fields (COSMOS, EGS, GOODS-North, GOODS-South and UDS) for passively evolving a.k.a. "red and dead" massive galaxies in the first 2 Gyr after the Big Bang, integrating and updating the work on GOODS-South presented in our previous paper. We perform SED-fitting on photometric data, with top-hat star-formation histories to model an early and abrupt quenching, and using a probabilistic approach to select only robust candidates. Using libraries without (with) spectral lines emission, starting from a total of more than 20,000 $z>3$ sources we end up with 102 (40) candidates, including one at $z=6.7$. This implies a minimal number density of $1.73 \pm 0.17 \times 10^{-5}$ ($6.69 \pm 1.08 \times 10^{-6}$) Mpc$^{-3}$ for $3<z<5$; applying a correction factor to account for incompleteness yields $2.30 \pm 0.20 \times 10^{-5}$. We compare these values with those from five recent hydrodynamical cosmological simulations, finding a reasonable agreement at $z<4$; tensions arise at earlier epochs. Finally, we use the star-formation histories from the best-fit models to estimate the contribution of the high-redshift passive galaxies to the global Star Formation Rate Density during their phase of activity, finding that they account for $\sim5-10\%$ of the total star formation at $3<z<8$, despite being only $\sim0.5\%$ of the total in number. The resulting picture is that early and strong star formation activity, building massive galaxies on short timescales and followed by a quick and abrupt quenching, is a rare but crucial phenomenon in the early Universe: the evolution of the cosmos must be heavily influenced by the short but powerful activity of these pristine monsters.