题目描述

题目译自 Open Olympiad in Informatics 2017 Day2 T1 「Открытая олимпиада по дизайну / Open Olympiad in Design」。

如果你不知道的话，通常在编程竞赛的准备过程中，参与者往往是过去曾经参加过类似竞赛的人。这非常方便：前编程奥林匹克选手通常不仅擅长编写程序，还懂得如何排版问题描述、设置测试系统以及处理许多其他有趣（或不那么有趣）的事务。但如果是由设计师来准备奥林匹克竞赛会怎样呢？

在一个虚构的宇宙中，正在举行由 $n$ 个设计师准备问题描述、一个设计师负责命名、一个设计师负责字体的中学生设计公开奥林匹克竞赛，该竞赛包含 $n$ 个问题。每个准备问题描述的设计师已经完成了自己问题的排版，但由于设计师是富有创造力且独立工作的人，每个人为问题标题预留的空间不同。具体来说，第 $i$ 个问题的设计预留了 $l_i$ 个字母的空间用于标题。

根据奥林匹克的规定，要求问题标题由 Unicode 字符组成，必须各不相同，并且按照字典序排列（参见备注）。字体设计师与命名设计师协商，希望后者能为问题挑选尽可能少使用不同字母的标题，以便字体设计师需要设计的字符图像数量最少。

在命名设计师构思标题的同时，字体设计师决定向你询问，为了构成所有问题的不同标题并使其按字典序排列，他需要绘制的最小不同字母数量是多少。假设 Unicode 中有足够多的字符，对于符合问题限制的任何输入数据都可以实现这一目标。注意，不允许 更改问题的顺序。

输入格式

输入数据的第一行包含一个整数 $n$ $(1 \leq n \leq 100000)$，表示奥林匹克竞赛中的问题数量。

第二行包含一序列整数 $l_1, l_2, \ldots, l_n$ $(1 \leq l_i \leq 10^{9})$，表示每个问题标题的长度。

输出格式

输出一个整数，即为所有问题构成不同标题所需的最小不同字符数量。

5
2 2 2 2 2

3

字典序的定义如下：长度为 $a$ 的字符串 $x_1 x_2 \ldots x_a$ 字典序小于 长度为 $b$ 的字符串 $y_1 y_2 \ldots y_b$，如果满足以下两个条件之一：

• 在第一个不同位置 $i$（即 $x_i \neq y_i$），第一字符串的字符小于第二字符串的字符，即 $x_1 = y_1, x_2 = y_2, \ldots, x_{i-1} = y_{i-1}, x_i < y_i$；
• 第一字符串是第二字符串的严格前缀，即 $a < b$ 且 $x_1 = y_1, x_2 = y_2, \ldots, x_a = y_a$。

在第一个样例中，可以使用字符 $\texttt{a} < \texttt{o} < \texttt{x}$ 来构成标题 $\texttt{aa}, \texttt{ao}, \texttt{ax}, \texttt{ox}, \texttt{xx}$。

4
3 1 2 2

2

在第二个样例中，可以使用两个字符 $\texttt{l} < \texttt{o}$ 来构成标题 $\texttt{lol}, \texttt{o}, \texttt{ol}, \texttt{oo}$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。