A-炼金术师_牛客练习赛79

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

爱德华以钢之炼金术师之名享誉全国，而今天他要完成弟弟阿尔冯斯提出的一个挑战。

已知爱德华和阿尔冯斯面前各摆了一块无限长的画布，画布上一开始均无任何颜色，且两块画布的最左端下标均设为 $0$ 。阿尔冯斯将使用 $n$ 次炼金术，第 $i$ 次炼金术会使他面前画布的 $[0,a_{i}]$ 区间染成第 $i$ 种颜色。

在阿尔冯斯使用完 $n$ 次炼金术后，爱德华也会使用若干次炼金术，每次炼金术他可以选择 $[1,n]$ 中的任意一种颜色，以及任意的一个右端点 $r$ ，将该画布的 $[0,r]$ 区间染成此次选择的颜色。

规定后面的染色会覆盖前面的染色，比如先将 $[0,2]$ 区间染成第 $2$ 种颜色，再将 $[0,1]$ 区间染成第 $3$ 种颜色，则此时 $[0,1]$ 区间的颜色是第3种颜色。

请问爱德华最少要使用多少次炼金术，才能把他面前的画布变成和阿尔冯斯的画布一样。

第一行一个正整数 $n$ ， $n\leq10^{6}$ 。

接下来 $n$ 个正整数 $a_{i}$ ， $a_{i}\leq10^{9}$ 。

输出爱德华最少要使用多少次炼金术。

示例1

复制

3
1 2 3

复制