你是一个一个一个救火队员哼哼哼啊啊啊啊啊啊啊啊啊，你早早爬起来救火，现在要去吃早饭。
食堂有nnn个窗口，从111到nnn编号，每个窗口有aia_iai公斤食物，你大手一挥，决定从lll到rrr号窗口，每个窗口都买下xxx公斤食物。
你必须保证在1≤l≤r≤n,∀l≤i≤r,x≤ai1 \leq l \leq r \leq n, \forall l \leq i \leq r, x \leq a_i1≤l≤r≤n,∀l≤i≤r,x≤ai的前提下，购买尽可能多的食物∑i=lrx\sum_{i=l}^r x∑i=lrx.
第一行一个整数nnn,为窗口个数。
接下来一行有nnn个整数aia_iai，为每个窗口的食物储量。
仅一个整数，为答案。
13 1 1 4 5 1 4 1 9 1 9 8 1 0
16
l=10,r=11,x=8l=10,r=11,x=8l=10,r=11,x=8
1≤n≤5×1061 \leq n \leq 5\times 10^61≤n≤5×106
0≤ai≤1050 \leq a_i \leq 10^50≤ai≤105