一个长度为 的非负整数构成的序列 , 每次操作你可以选择一个区间 ,将区间内的数字全部减一,进行一次这样的操作的代价为 ,你想要进行若干次操作将这个序列的数字全部变成零,这样做的总代价是每次操作代价之和。
你希望进行的操作次数最少,在满足操作次数最少的前提下,求出你的最小总代价和最大总代价。
由于答案可能很大,请将答案模 输出,注意是将最小最大代价取模输出,而不是代价取模后的值最大或最小。
第一行一个正整数 ,表示序列长度.
接下来一行, 个非负整数,表示序列中的元素 .
一行两个非负整数,表示最小代价和最大代价取模后的值.
6 1 1 4 5 1 4
40 52
7 1 9 1 9 8 1 0
57 73
3 1000000000 1000000000 1000000000
999999944 999999944