题目描述
众所周知,zrq 在机房不仅可以学物理,甚至可以学竞赛!
zrq 看着自己的一堆物理书(每本物理书有权值,表示难易度,即 ai),同时想出了一对 l,r。他先将这些书在地上排成一行,他想知道对于某本书 i,所有经过这本书、且长度在 [l,r] 之间的连续子序列中,最大的连续子序列的权值和。即对于每一个 i ,求:
fi=1≤x≤i≤y≤n且l≤y−x+1≤rmaxk=x∑yak
输入格式
第一行三个整数 n,l,r,表示序列长度、区间范围。
第二行 n 个整数,其中第 i 个整数表示 ai。
输出格式
一行 n 个整数,第 i 个整数表示 fi
样例
5 1 3
-1 -6 7 7 -4
0 8 14 14 10
数据范围与提示
对于 10% 的数据,保证n≤10
对于另外 10% 的数据,保证 ∀i,j∈[1,n]∩Z,ai=aj
对于另外 10% 的数据,保证 r−l+1≤10
对于另外 10% 的数据,保证 ∀i∈[1,n]∩Z,ai=i
对于另外 10% 的数据,保证 ∀i∈[1,n]∩Z,ai≥0
对于另外 10% 的数据,保证 ∀i∈[1,n]∩Z,0≤∣ai∣≤10
对于另外 10% 的数据,保证 ∀i∈[1,n]∩Z,ai=0
对于 100% 的数据,保证1≤l≤r≤n≤105,0≤∣ai∣≤105