题目描述

FJ 决定给奶牛放假。假期必须是在 $1\sim N$ 天内选择的一段连续区间，每一天都有一个享受指数 $W_i$。奶牛要求假期长度不能短于 $P$ 天，也不能超过 $Q$ 天。请计算奶牛能够获得的最大享受指数总和。

输入格式

第一行输入三个整数 $N,P,Q$，分别表示总天数、假期最短天数和假期最长天数。

第二行输入 $N$ 个整数 $W_1,W_2,\ldots,W_N$，表示每天的享受指数。

输出格式

输出一个整数，表示长度在 $[P,Q]$ 内的连续区间最大和。

5 2 4
-9 -4 -3 8 -6

5

数据范围与提示

• $1 \le P \le Q \le N \le 200000$
• $-10^9 \le W_i \le 10^9$
• 样例选择第 $3$ 天到第 $4$ 天，享受指数为 $-3+8=5$。
• 可用前缀和配合单调队列维护可选左端点的最小前缀和。

来源

单调队列