{"raw_statement":[{"iden":"statement","content":"在你的帮助下，Rebecca 的风景照现在登上了她的杂志的最新一期的封面。然而，似乎有些读者对这张照片还不满意。特别是，他们似乎认为照片中的山是假的！\n\n为了简单起见，我们可以把这张照片描述为一个由 $N$ 列像素组成的序列。在第 $i$ 列，从底部开始的前 $h_{i}$ 个像素是山。她的读者只有在照片中包含一个山峰时，才会相信这是一座真正的山。也就是说，如果存在某个下标 $p$，满足 $1 \\leq p \\leq N$，使得 $h_{1} \\leq h_{2} \\leq \\cdots \\leq h_{p} \\geq \\cdots \\geq h_{N-1} \\geq h_{N}$。\n\n幸运的是，Rebecca 还可以付钱给她的编辑修改照片并重新印刷杂志。不过，她的倒霉的是，编辑们对他们的工作有一个非常奇怪的定价方案。Rebecca 唯一能编辑照片的方法是给她的编辑发送包含三个整数 $(i, j, k)$ 的电子邮件，满足 $1 \\leq i<j<k \\leq N$ 且 $h_{i}>h_{j}<h_{k}$。编辑们会在第 $j$ 列添加一个额外的山的像素（即 $h_{j}$ 增加 $1$），费用是 $h_{i}+h_{j}+h_{k}$。注意 $h_{j}$ 的变化可能会影响未来编辑的费用。\n\n为了取悦她的读者，Rebecca 想要编辑照片，让他们相信这里有一座真正的山。你能告诉她需要花费的最小费用吗？"},{"iden":"input","content":"第一行包含一个整数 $N$。\n\n第二行包含 $N$ 个用空格分隔的整数，表示 $h_{1}, h_{2}, \\ldots, h_{N}$。"},{"iden":"output","content":"输出 $T$ 对 $10^{6}+3$ 取模的结果，其中 $T$ 是 Rebecca 为了取悦她的读者而需要花费的最小费用。"},{"iden":"note","content":"Rebecca 可以发送两封电子邮件，第一封包含三个整数 $(2,6,7)$，第二封包含三个整数 $(1,2,5)$。第一封电子邮件花费 $5$，使 $h_{6}$ 增加 $1$，而第二封电子邮件花费 $9$，使 $h_{2}$ 增加 $1$。\n\n最终照片中的 $h_{i}$ 值将是 $[3,3,4,5,4,2,2,1]$。\n\n对于所有的数据，有 $3\\leq N \\leq 10^6$，$1 \\leq h_{i} \\leq 10^{9}$。\n\n| 子任务编号|\t分值\t|$N$ 的范围\t|$h_{i}$ 的范围和限制|\n| :-:| :-:| :-:| :-:|\n|1|\t12|\t$ N \\leq 5000$\t|$1 \\leq h_{i} \\leq 100, \\exists p \\in [1,N], h_{1} \\geq h_{2} \\geq \\cdots \\geq h_{p} \\leq \\cdots \\leq h_{N-1} \\leq h_{N}$|\n|2|\t12\t|\t$ N \\leq 5000$\t|$1 \\leq h_{i} \\leq 100$|\n|3|\t12\t|\t$ N \\leq 5000$\t|$1 \\leq h_{i} \\leq 10^{6}$|\n|4|\t12\t|\t$ N \\leq 5000$\t|$1 \\leq h_{i} \\leq 10^{9}$|\n|5|\t16\t|$N \\leq 10^{6}$|\t$1 \\leq h_{i} \\leq 100$|\n|6|\t20\t|$ N \\leq 10^{6}$|$1 \\leq h_{i} \\leq 10^{6}$|\n|7|\t16\t|$ N \\leq 10^{6}$|$1 \\leq h_{i} \\leq 10^{9}$|"}],"translated_statement":null,"sample_group":[["8\n3 2 4 5 4 1 2 1","14"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}