  A generic prediction of general relativity is that the cosmological linear
density growth factor $D$ is scale independent. But in general, modified
gravities do not preserve this signature. A scale dependent $D$ can cause time
variation in gravitational potential at high redshifts and provides a new
cosmological test of gravity, through early time integrated Sachs-Wolfe (ISW)
effect-large scale structure (LSS) cross correlation. We demonstrate the power
of this test for a class of $f(R)$ gravity, with the form $f(R)=-\lambda_1
H_0^2\exp(-R/\lambda_2H_0^2)$. Such $f(R)$ gravity, even with degenerate
expansion history to $\Lambda$CDM, can produce detectable ISW effect at $z\ga
3$ and $l\ga 20$. Null-detection of such effect would constrain $\lambda_2$ to
be $\lambda_2>1000$ at $>95%$ confidence level. On the other hand, robust
detection of ISW-LSS cross correlation at high $z$ will severely challenge
general relativity.
