P2075 Interval LIS

Given a permutation $p$ of $1\sim n$, there are $q$ queries. Each query asks for the length of the longest increasing subsequence within the interval $[l,r]$.

The first line contains two positive integers $n,q$. The second line contains $n$ positive integers, representing the permutation $p$. Then $q$ lines follow, each containing two positive integers $l,r$, representing a query.

For each query, output the corresponding answer.

| Subtask ID | $n$ | $q$ | Score | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^3$ | $10^3$ | $20$ | | $2$ | $10^3$ | $10^5$ | $30$ | | $3$ | $10^5$ | $10^5$ | $50$ | For all testdata, $1\leq n,q\leq10^5$, $1\leq l\leq r\leq n$. Translated by ChatGPT 5