Time Limit: 1000 MS    Memory Limit: 131072 K 


Description

jibancanyang和妹子去海边玩,沙滩上有若干个小沙堆,jibancanyang有强迫症,希望沙堆的高度是从坐到右非递减的. 为了实现这个目的,可以任意加减任意一个(或者多个)沙堆的高度(甚至挖一个坑让高度为负数). 可是他很懒,他希望让自己加减的高度和最小,来实现这个目的,问最少加减多少高度沙子可以达到这个目的?

Input

有多组输入。 对于每组数据 输入包含多行,每行一个数n(1 <= n <= 3000), 然后跟着n个数h(0 < h < 1000, 000, 000),表示沙堆的高度

Output

一行一个数表示最小加减的高度和,结果对19970303取余数

Sample Input

3 1 2 1

Sample Output

1 hint:可以把第二个沙堆减一高度,或者第三个沙堆加一高度都可.