该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

本题需要使用文件输入输出，文件名为flowers.in、flowers.out。

题目描述

小z在等待朋友，他和朋友计划出去游玩，但是朋友来的实在太慢了，无聊的他在研究路边的小花。

他发现路边一共有$n$朵小花，小花排成一排，每朵小花的高度为$h_i$。

在等待朋友的每一分钟，小z都会让小花的高度减少，直到所有小花减少到$0$的时候，朋友就到了！

小花们高度减少的规则也很简单，每一分钟，对于所有小花$i(1 \leq i \leq n)$ ，如果$i=n$或者$h_i > h_{i+1}$，那么这些小花的高度就会变$max(0,h_i-1)$。其中$h_i$是第$i$朵小花的高度。

那么，小z还要等朋友多少分钟呢？

问题虽然简单！但等着急躁的小z根本无心计算！这个简简单单的问题就只能交给你来解决啦！

输入格式

每个测试用例的第一行都包含一个整数 $n$ ( $1 \le n \le 10^5$ ) --花朵的数量。

每个测试用例的第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$ ( $1 \le h_i \le 10 ^ 9$ ) --花朵的高度。

输出格式

对于每个测试用例，输出一个整数 - 所有 $1 \le i \le n$ 在 $h_i=0$ 之前经过的分钟数。

样例

3
1 1 2

4

2
3 1

3

1
9

9

5
7 4 4 3 2

7

提示

对于10%的数据，$n$不会超过$100$.

对于50%的数据, $h_i$ 不会超过$10000$.

对于100%的数据，满足上文的输入描述。