#P11301. [COTS 2023] 下 Niz

[COTS 2023] 下 Niz

题目描述

给定长度为 NN 的序列 aa,求满足以下条件的 (l,r)(l,r) 对数:

  • 1≤l≤r≤N1\le l\le r\le N;
  • al,al+1,⋯ ,ar−1,ara_l,a_{l+1},\cdots,a_{r-1},a_r 是 1∼r−l+11\sim r-l+1 的排列。

输入格式

第一行,一个正整数 NN,表示序列长度;

第二行,NN 个正整数,描述序列 aa。

输出格式

一行一个整数,即满足条件的 (l,r)(l,r) 的数量。

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

3

输入输出样例 #2

输入 #2

5
3 2 1 2 3

输出 #2

5

输入输出样例 #3

输入 #3

7
2 1 3 1 2 3 4

输出 #3

8

说明/提示

样例解释

样例 33 解释:满足条件的 (l,r)(l,r) 有 (2,2),(1,2),(1,3),(4,4),(4,5),(4,6),(4,7),(3,5)(2,2),(1,2),(1,3),(4,4),(4,5),(4,6),(4,7),(3,5)。

数据范围

对于 100%100\% 的数据,保证:

  • 1≤N≤1061\le N\le 10^6;
  • 1≤ai≤N1\le a_i\le N。
子任务编号 分值 约束
11 1313 每个数只在序列中出现一次
22 2020 N≤5 000N\le 5\, 000
33 3333 N≤50 000N\le 50\, 000
44 3434 无额外约束