Minimum Deletions for Sorted - Implementation

Use the binary search LIS with $\leq$ comparison. In the tails array, use lower_bound for strictly increasing, upper_bound for non-decreasing. For non-decreasing: when element $x$ equals $tails[k]$, we can extend (not replace). Use upper_bound to find insertion point.

Alternatively, for strictly increasing on an array with duplicates: make elements unique by pairing with indices: $(value, index)$. Sort lexicographically. Time: $O(n \log n)$ with binary search, $O(n^2)$ with naive DP. Space: $O(n)$ for the tails array. The binary search approach handles both variants.

Time complexity: $O(n^2)$.

Space complexity: $O(n)$.