数组分组
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
一个长度为 n 的数组 a，我们可以把它分成任意组，每一组是一段连续的区间。比如数组 1,2,3,4,5 可以分成 (1, 2), (3, 4, 5) 两个组。
每个分组都有一个权值，这个权值就是分组里面每个数的乘积对 1000 取模的结果。
对于数组 a 的一个分组方案，总权值就是每个分组的权值和。
那么对于数组 a，分组以后最大的权值和是多少？
输入格式
输入第一张一个整数。
接下来一行 n 个整数，表示数组 a，数组中每个元素都小于等于 100。
输出格式
数组最大的分组权值和。
输出时每行末尾的多余空格，不影响答案正确性
要求使用「文件输入输出」的方式解题，输入文件为 split.in，输出文件为 split.out
样例输入
7
52 26 1 36 72 48 43
样例输出
1596