题意：

给 $n$（$\le 10^6$）的排列 $a$，再给 $q$（$\le 20$）个 $k$（$\le 10^6$）。对于每个 $k$，求出 $a$ 的一个最长不下降子序列 $b$，使得 $\sum{\ln(b_i-b_{i-1}+k)}$ 最大。对每组询问都输出一个答案。

首先显然有一种 $nq \log^2{n}$ 的 cdq 做法。但是题目不让用。

首先，$\ln$ 显然满足四边形不等式。然后仔细观察发现，假设有三个数 $a, b, c$，那么选择 $a, c$ 一定略于 $a, b, c$。

这启发我们对原数列分层。设 $len_i$ 表示从 $i$ 开始的 LIS。定义 $S_i = {x

len_x = i}$。那么以下标从小到大遍历 $S_i$ 的话，值一定递减。

根据多一个 log 的 cdq 做法，我们可以定义 $f_i$ 表示从 i 开始只考虑 $\cup_{j \le len_i} S_j$ 中的位置，得到的最大值。那么转移：

$f_{i} = \max_{len_{j} = len_{i} - 1 \land j \ge i \land a_j \ge a_i} f_{j}$。但是，由于同一层中 a 随着下标递增而递减。所以，满足条件的 $j$ 在那一层中是连续的！那么分治乱搞即可。

复杂度：$O(nq \log n)$