CF455E Function

Serega 和 Fedya 正在玩函数。一天，他们遇到了一个非常有趣的函数。这个函数定义如下： - $ f(1,j)=a[j] $，其中 $ 1 \leq j \leq n $。 - $ f(i,j)=\min(f(i-1,j), f(i-1,j-1)) + a[j] $，其中 $ 2 \leq i \leq n $ 且 $ i \leq j \leq n $。 其中 $ a $ 是一个长度为 $ n $ 的整数数组。 Serega 和 Fedya 想知道这个函数在某些点上的取值。但他们不想手动计算这些值，所以他们请求你帮助他们。

第一行包含一个整数 $ n $（$ 1 \leq n \leq 10^{5} $），表示数组 $ a $ 的长度。下一行包含 $ n $ 个整数：$ a[1], a[2], ..., a[n] $（$ 0 \leq a[i] \leq 10^{4} $）。 接下来一行包含一个整数 $ m $（$ 1 \leq m \leq 10^{5} $），表示询问的数量。接下来的 $ m $ 行中，每行包含两个整数：$ x_i, y_i $（$ 1 \leq x_i \leq y_i \leq n $）。每条询问表示 Fedor 和 Serega 想知道 $ f(x_i, y_i) $ 的值。

输出 $ m $ 行，每行一个答案，分别对应每个询问的函数值。

由 ChatGPT 5 翻译