33OJ
登录 注册

#ABC485G. 相似相邻子数组

相似相邻子数组

相似相邻子数组

题目描述

给定一个长度为 NN 的正整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N)。

求满足以下所有条件的整数三元组 (a,b,c)(a,b,c) 的个数:

  • 0≤a<b<c≤N0 \le a < b < c \le N;
  • b−a=c−bb-a = c-b;
  • 在 1≤i≤b−a1 \le i \le b-a 中,恰好只有一个整数 ii 满足 Aa+i≠Ab+iA_{a+i} \neq A_{b+i}。

输入格式

输入第一行为一个整数 NN。

第二行为 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出一行一个整数,表示满足条件的三元组个数。

7
1 2 1 3 1 2 1
10

样例 1 解释

满足条件的三元组共有以下 1010 个:

$(0,1,2),(0,2,4),(1,2,3),(1,3,5),(2,3,4),(2,4,6),(3,4,5),(3,5,7),(4,5,6),(5,6,7)$。

2
1000000000 1000000000
0
6
1 2 3 1 2 4
6

数据范围

对于所有测试数据,保证:

  • 2≤N≤2×1052 \le N \le 2 \times 10^5;
  • 1≤Ai≤1091 \le A_i \le 10^9;
  • 所有输入值均为整数。

子任务

本题共 20 个测试点,按测试点计分:

测试点 分值 每个测试点 特殊性质
1∼61 \sim 6 3030 55 N≤2000N \le 2000
7∼127 \sim 12 N≤5×104N \le 5 \times 10^4
13∼2013 \sim 20 4040 无特殊限制

每个测试点单独评分,全部测试点的得分之和即为本题得分。