题目描述
某只股票的价格每天重复相同的规律。一天分为 n 个等长时段,第 i 个时段的价格为 ai。第 n 个时段结束后,紧接着是次日的第 1 个时段。
给定 q 个工作时间段。第 i 个时间段从 li 开始,到 ri 结束,两端均包含:
- 若 li≤ri,时段顺序为 li,li+1,…,ri;
- 若 li>ri,时段顺序为 li,li+1,…,n,1,…,ri。
每个工作时间段内最多完成 k 次交易。每次交易先买入一股,再在严格更晚的时段卖出,收益为卖出价格减买入价格。任何时候最多持有一股股票,卖出后才能再次买入。全部买卖必须在当前工作时间段内完成。
也可以不交易,此时收益为 0。对每个工作时间段,独立求出最大总收益。
输入格式
第一行包含三个整数 n,k,q。
第二行包含 n 个整数 a1,…,an。
接下来 q 行,每行包含两个整数 li,ri。
输出格式
输出 q 行,第 i 行为第 i 个工作时间段的最大总收益。
样例
6 2 3
3 1 4 1 5 9
2 5
5 2
4 4
7
4
0
数据范围与特殊保证
- 1≤n≤105,1≤k≤800,1≤q≤3×105;
- 1≤ai≤106,1≤li,ri≤n。
记当前工作时间段的时段数为 leni。若 li≤ri,则 leni=ri−li+1;否则 leni=n−li+1+ri。
每个询问的 li 和 leni 分别从 [1,n] 和 $[\max(1,\lfloor0.15n\rfloor),\max(1,\lfloor0.85n\rfloor)]$ 独立均匀随机生成,ri 由它们唯一确定。 n=1 时总是得到 (1,1)。