Before revision:  This is the first lower bound on LIS estimation that is significantly larger than the query complexity of testing sortedness. In contrast, there is an adaptive algorithm (Saks, and Seshadhri; 2017) for the same problem with query complexity polylogarithmic in n. Next, we design nonadaptive LIS estimation algorithms whose complexity is parameterized in terms of the number of distinct values r in the array  .
After revision:  Next, we design nonadaptive LIS estimation algorithms whose complexity is parameterized in terms of the number of distinct values r in the array .