#P12451. [UOI 2023] An Array and Range Additions

[UOI 2023] An Array and Range Additions

题目描述

给定一个长度为 nn 的整数数组 aa。

你可以通过加法操作来修改数组。要执行加法操作,你需要依次完成以下三个步骤:

  • 选择任意整数 xx。
  • 选择数组中的任意子数组 [l;r][l;r]。
  • 将 xx 加到所选子数组的每个元素上(即对 l≤i≤rl \le i \le r 执行赋值操作 ai←(ai+x)a_i \leftarrow (a_i + x))。

找到使数组 aa 中所有元素两两不同的最小加法操作次数。

输入格式

第一行包含一个整数 nn(1≤n≤2⋅1051 \le n \le 2 \cdot 10^5)——数组的长度。

第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \ldots, a_n(1≤ai≤1091 \le a_i \le 10^9)——数组的元素。

输出格式

输出一个整数——使数组 aa 中所有元素两两不同的最小加法操作次数。

输入输出样例 #1

输入 #1

3
1 2 3

输出 #1

0

输入输出样例 #2

输入 #2

5
2 3 2 3 2

输出 #2

2

输入输出样例 #3

输入 #3

9
2 3 1 1 3 2 1 3 3

输出 #3

2

说明/提示

在第一个样例中,数组 aa 的所有元素已经是两两不同的。

在第二个样例中,应用两次加法操作,参数分别为 x=−3x=-3、l=1l=1、r=2r=2 和 x=−1x=-1、l=1l=1、r=3r=3 后,数组 aa 变为 [−2,−1,1,3,2][-2, -1, 1, 3, 2]。

在第三个样例中,应用两次加法操作,参数分别为 x=−3x=-3、l=4l=4、r=8r=8 和 x=−10x=-10、l=7l=7、r=9r=9 后,数组 aa 变为 [2,3,1,−2,0,−1,−12,−10,−7][2, 3, 1, -2, 0, -1, -12, -10, -7]。

评分标准

  • (99 分):数组 aa 的所有元素均为 11。
  • (1515 分):对于 1≤i≤n1 \le i \le n,1≤ai≤21 \le a_i \le 2;对于 1≤i<n1 \le i < n,ai≤ai+1a_i \le a_{i+1}。
  • (1414 分):n≤8n \le 8。
  • (1717 分):a1=ana_1 = a_n。
  • (1212 分):n≤2000n \le 2000。
  • (1212 分):对于 1≤i≤n1 \le i \le n,1≤ai≤1001 \le a_i \le 100。
  • (2121 分):无额外限制。