思路与做法

关键观察

对固定的右端点 $r$，设每个值在前缀 $[1,r]$ 内的最后一次出现位置为 $\text{last}_r[v]$。 那么一个值 $v$ 会出现在 $[l,r]$ 中，当且仅当 $\text{last}_r[v]\ge l$。 因此

题目内容

钟师在远古祭坛铺设了 $n$ 口钟阵，每口钟的编号记录在数组 {$a_1,a_2,...,a_n$} 中;

对任意区间 $[l,r]$ ，记钟面编号差 $△_面=a_r-a_l$ ，并令 $g(l,r)$ 表示区间内不同钟声的种类数;

于是区间的净余谐振能量定义为

$△_{净余}=(a_r-a_l)-g(l,r)$

请你在所有 $1≤l≤r≤n$ 的区间中，求得最大的 $△_{净余}$。

输入描述

第一行输入一个整数 $n(1≤n≤2×10^5)$ ，钟阵长度;

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤ a_i≤ n)$ 表示每口钟的编号。

输出描述

输出一个整数，表示所有区间中最大净余谐振能量。

样例1

输入

5
1 3 1 5 3

输出

2

说明

选择区间 $[3,4]$ ：

• 编号差 $5-1=4$ ;

• 不同种类 $g(3,4)= 2$ ;

• 编余谐振$4-2=2$。

样例2

输入

5
1 2 3 4 5

输出

-1