The quenching process of galaxies poses a challenge to theoretical models, which struggle to reproduce the quenched fractions from low-redshift to high-redshift. The main issues can be summarized as `over-quenching' of low-mass galaxies at low-redshift, and 'under-quenching' of massive galaxies at high-redshift. By conducting tests on the semi-analytic model GAEA, we find the former challenge is addressed by implementing a milder environmental stripping on hot gas and cold gas; while the latter challenge is resolved by implementing AGN-driven outflows. The model now reproduces a wide range of observational results, including the observed quenched fractions and number densities up to redshift z~3-4. We therefore use the model to investigate quenching mechanisms and large-scale environments of the first massive quenched galaxies. High-redshift massive quiescent galaxies reside in a broad range of environments, from voids, to filamentary structures and knots. Among various indicators of environments, the large-scale over-density can be used as a good predictor of their halo mass at z=0.