P5097 [USACO04OPEN] Cave Cows 2

There is a long passage in a cave. It is made up of $N$ segments ($1 \leq N \leq 25000$) connected end to end, numbered $1 \ldots N$. Each segment has a threshold value in the range $[1,10^9]$. If a cow passes through segments $i \ldots j$ in order, then the cow’s weight index must not exceed the minimum threshold among segments $i \ldots j$. Bessie has $Q$ questions ($1 \leq Q \leq 25000$) and wants to ask you for the minimum threshold value from segment $i$ to segment $j$.

The first line contains $N$ and $Q$. The next $N$ lines contain the threshold value of each segment. After that, the next $Q$ lines each contain two integers, corresponding to $i$ and $j$ in the questions ($i < j$).

For each query, output the answer.

Translated by ChatGPT 5