点集合 \(\lbrace (i, y) \mid y \geq R _ i \rbrace\) の凸包を \(S\) として、数列 \(T = (T _ 1, T _ 2, \dots, T _ N)\) を \(T _ i = \min \lbrace y \mid (i, y) \in S \rbrace\) と定義します。 砕けた言い方をすると、\(R\) の lower convex hull を取って \(T\) としています。 このようにして得られた \(T\) は、問題文中の \(L\) についての条件以外を満たす \(A\) のなかで”最大”のものになっています。 厳密には、以下の条件を満たす任意の \(A\) に対し \(A _ i \leq T _ i\) が成り立ちます。

• \(1 \leq i \leq N\) を満たすすべての整数 \(i\) に対して \(A _ i \leq R _ i\) が成り立つ。
• \(2 \leq i \leq N - 1\) を満たすすべての整数 \(i\) に対して \(A _ {i - 1} + A _ {i + 1} \geq 2 A _ i\) が成り立つ。

これは凸包の定義から導くことができます。

したがって、\(T\) が \(L _ i \leq T _ i\) を満たすなら Yes、満たさないなら No が答えです。 \(T\) は Andrew’s monotone chain などのアルゴリズムを用いて \(O(N)\) 時間で計算できます。