杂题选记
A
Statement
给定一个长度为 \(n\) 的单调不降的整数数列 \(A\)。
有 \(q\) 次相互独立的询问，每次询问给定 \(l,r\)，从时刻 \(0\) 起，每个时刻对于 \(\forall i\in \left[l,r\right)\) 且 \(A_i \textcolor{red}{\lt} A_{i+1}\)，令 \(A_i \gets A_i+1\)。问最少经过多少时刻后，\(\forall i \in \left[l,r\right)\)，都满足 \(A_i=A_r\)?
\(1\leq n,q\leq 10^6\)，\(|A_i|\leq 10^9\)。