Let $$$L_i$$$ be the nearest greater element on the left, and $$$R_i$$$ be the nearest greater element on the right. These can be calculated in $$$\mathcal{O}(n)$$$ with monotonic stack.

From the value $$$i$$$ we can go to any value in $$$[L_i + 1, R_i - 1]$$$ that's strictly smaller than $$$h_i$$$. So we will calculate the DP in increasing order of $$$h_i$$$. The formula will be:

We can calculate this with a segment tree. We also have to take care of duplicates by calculating them at the same time and then updating the segment tree.

Let $$$P_i$$$ be the nearest greater element on the right. This can be calculated with monotonic stack. Now the query becomes: "How many times can you perform the assignment $$$l = P_l$$$ while $$$l \le r$$$?". This can be solved with binary lifting.

This can be solved using merge sort tree. In each node of the segment tree, we will store all the elements in the range in nondecreasing order.

For each query, we will decompose it into $$$\mathcal{O}(\log n)$$$ nodes, and each node, we will count the number of values between $$$c$$$ and $$$d$$$ in $$$\mathcal{O}(\log n)$$$ using binary search. This way, we can answer each query in $$$\mathcal{O}(\log^2 n)$$$, which is fast enough.

Let $$$S_i$$$ be the nearest equal element on the right, or $$$∞$$$. If there's an $$$i$$$ in $$$[l, r]$$$ such that $$$P_i \le r$$$, then $$$a_i = a_{P_i}$$$. That means not all values in $$$[l, r]$$$ are distinct. To check if such $$$i$$$ exists in $$$[l, r]$$$, check the minimum $$$P_i$$$. This can be done with a segment tree.

In each update, $$$\mathcal{O}(1)$$$ values change, so it can done in $$$\mathcal{O}(\log n)$$$ per query.

The average prime gap is $$$\mathcal{O}(\log n)$$$. So the trivial solution actually works in $$$\mathcal{O}(\sqrt{n} \log n)$$$. It can also be done in $$$\mathcal{O}(\log n)$$$ using randomized primality checks.

Imagine a functional graph with $$$n$$$ edges of the form $$$i \rightarrow p_i$$$. Let $$$L_1, L_2, ..., L_k$$$. The answer will be LCM(L_1, L_2, ..., L_k). This can be calculated by factorizing in $$$\mathcal{O}(n \sqrt{n})$$$ or $$$\mathcal{O}(n \log n)$$$ with sieve.

This can be done with monotonic queue, which allows adding an element at the back, removing the element from the front, and extracting the minimum. https://cp-algorithms.com/data_structures/stack_queue_modification.html#queue-modification-method-1

This can be done with a std::map to maintain the frequency of each value.

This can be done with a std::map to maintain the frequency of each value, as we as a std::set containing (frequency, values) pairs.

This can be done with an array to maintain the frequency of each value (since only values $$$\le k$$$ are relevant for th mex), as well as a std::set of excluded values.

This can be done by maintaining the number of inversions and an ordered set.

When adding a new element $$$x$$$, we will add the number of elements greater than $$$x$$$ to the inversion counter (since $$$x$$$ is at the end of the subarray).

When removing an element $$$x$$$, we will subtract the number of elements less than $$$x$$$ to the inversion counter (since $$$x$$$ is at the start of the subarray).

Distinct values, mode, MEX, and inversions can all be solved using a segment tree and coordinate compression.

We can use mergesort. This uses $$$n \log n$$$.

Let's query chair $$$1$$$ and chair $$$N$$$. If they're equal, then we have found a solution. Otherwise, we can solve using binary search.

Let's query chair $$$x = \frac{N+1}{2}$$$. If $$$x$$$ is odd and chair $$$1$$$ is equal to chair $$$x$$$, we can guarantee a solution in $$$[x, n]$$$. Same can be said if $$$x$$$ is even and chair $$$1$$$ is not equal to chair $$$x$$$. Otherwise, there always exists a solution in $$$[1, x]$$$.

This solution uses exactly $$$2 + \lceil \log_2 n \rceil$$$ queries, which is at most $$$20$$$.