subsequence not subarray.

counterexample:

a = [1, 2, 1, 3, 1, 4, 1, 5], x = 5

ans = true, but your condition is false.

Calculating LIS in O(nlog(n)) is not an option here ?

What does coordinate compression means? Google search hasn't got me anywhere.

My solution for the LIS:

let $$$a[i]$$$ be the length of LIS wich the last element is $$$i$$$

then $$$a[i]$$$ = maximum of $$$a[0...i-1]+1$$$

finding the maximum can be done using a fenwik tree or a segment tree. Is this different from your solution? If so can you explain me yours

Edit: Oh it just occurred to me. we can't do this if maximum element is too large. I guess coordinate compression is to solve that issue?

Good thought, but this isn't a valid proof. There's plenty of problems where answering "is the answer bigger than or equal to X?" is faster than answering "what is the answer?". Since the latter can be obtained from the former using binary search, a correct lower bound, only knowing the fact that answering "what is the answer?" has a lower bound of $$$O(n \log n)$$$, is $$$O(\frac{n \log n}{\log n}) = O(n)$$$, but this ends up being useless here.

Well technically checking whether the LIS is of length at least X could be faster than calculating the LIS. For example, the problem of checking whether a palindrome of length X exists in a string can be carried out in linear time with hashes, while a binary search + hashes solution takes $$$O(n \; log \; n)$$$ time to compute the longest palindrome. However, the longest palindrome can be computed in linear time with other methods (such as Manacher's algorithm or eertree).