Type: Default 1000ms 256MiB

数组分组

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(1n1000) n(1 \le n \le 1000)

接下来一行 n 个整数,表示数组 a,数组中每个元素都小于等于 100。

输出格式

数组最大的分组权值和。

输出时每行末尾的多余空格,不影响答案正确性

要求使用「文件输入输出」的方式解题,输入文件为 split.in,输出文件为 split.out

样例输入

7
52 26 1 36 72 48 43

样例输出

1596

3月9日周六8:10

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
11
Start at
2024-3-9 8:00
End at
2024-3-13 12:00
Duration
100 hour(s)
Host
Partic.
3