問題文
N PA 实验室成员左右排列。从左边开始 i PA 实验室成员的身高是 A_i 。
您的工作是执行以下操作: 0 反复不止一次,研究组的成员按照背部的顺序排成一排,也就是任意 i\ (1\leq i\leq (列中的成员数)-1) 反对 (从左起 从第 i 第一个成员的高度 目标是确保)<(从左起 从第 i+1 第一个成员的高度 目标是确保) 成立。
- 当前排队的 PA 实验室成员数量。 M 作为整数 替换为 l,\ r\ (1\leq l\leq r\leq M) 。从选择时的左侧开始 l 成员的高度 当 L、r 成员的高度 当 R 时,成本 从左边开始支付 L+R 从队列中删除第 l,\ l+1,\ldots,\ r 个 PA 实验室成员。
完成任务所需支付的最低总成本是多少?
即使队伍中没有人,也假设他们按照身高顺序排列,并且即使重复操作,成员的高度也不会改变。
制約
- 所有输入均为整数。
- 1\leq N\leq2×10^5
- 1\leq A_i\leq N
- A_i≠A_j\ (i≠j)
入力
输入是按以下格式从标准输入给出的。
\(N\) \(A_1\) \(A_2\) \(\ldots\) \(A_N\)
出力
请输出需要支付的总费用的最小值。 不要忘记输出末尾的换行符。
入力例1
4 3 4 1 2
出力例1
3
l=3,\ r=4 作为 1 最好只执行一次该操作。
入力例2
6 1 2 3 4 5 6
出力例2
0
1 最好不要多次操作。
入力例3
7 1 5 4 7 2 3 6
出力例3
3