#P3316. JC loves Mkk

    ID: 2504 传统题 1000ms 512MiB 尝试: 1357 已通过: 311 难度: 7 上传者: 标签>难度分类提高+/省选-排序与序列处理二分答案一维前缀和单调队列滑动窗口最值构造与建模复制数组处理环奇偶分组数论欧几里得算法CF2300杂项分数规划

JC loves Mkk

题目描述

JC 和 Mkk 去买糖果。柜台上有一串围成圆环的糖果,共 nn 颗。第 ii 颗糖的美味值为 aia_i,第 nn 颗和第 11 颗相邻。

原题糖果环示意图

顾客可以选择沿圆环连续的一段糖果,每颗糖在所选段中只出现一次。一段糖果的美味值等于其中各颗糖的美味值的算术平均值。

JC 要选择的糖果颗数必须是 [L,R][L,R] 里的偶数,以便两人平分糖果。求满足条件的最大平均美味值。

输入格式

从标准输入读取。第一行是三个整数 n,L,Rn,L,R。第二行是 nn 个整数 a1,…,ana_1,\ldots,a_n,按圆环顺序给出各颗糖果的美味值。

输出格式

向标准输出写入。输出一行。答案为整数时直接输出该整数,否则输出最简分数 P/QP/Q。

样例 1

5 3 4
3 1 2 4 5
7/2

样例说明

可选择除美味值为 11 的糖果之外的另外四颗。沿圆环它们连续,总美味值为 1414,平均值为 7/27/2。

数据范围

1≤L≤R≤n≤1051\le L\le R\le n\le10^5,0≤ai≤1090\le a_i\le10^9。保证存在符合长度条件的选法。原题数据由随机生成。