题目描述

悖论的面前有 $n$ 名实力各异的敌人排成一列。他们的实力构成一个长度为 $n$ 的排列$^\texttt{[1]}$$p_1,p_2,\dots,p_n$，其中 $p_i$ 表示从左往右第 $i$ 名敌人的实力。 悖论想用她的动能卡宾枪一举贯穿敌人！然而，这把武器只能贯穿位置连续的偶数名敌人，并且这些敌人的实力必须从左往右依次为 $x,x+1,\ldots,x+k-1$，其中 $x$ 为任意正整数，$k$ 为敌人的数量且必须为偶数。 如此苛刻的条件，让悖论十分头疼。好在，她可以投出一种名为“悖论置换”的奇特物质，改变敌人的站位。每次使用时，她可以选择三名相邻的敌人，将他们从左往右的顺序由 $(x,y,z)$ 变为 $(y,z,x)$。 现在，悖论想知道：有多少个偶长度的非空子数组$^\texttt{[2]}$ $[l,r]$，满足仅对该数组内的敌人进行若干次（可以为零）“悖论置换”后，能够让区间内的全部敌人被动能卡宾枪一次贯穿。不同子数组独立判断，均以原排列 $p$ 为初始状态。由于悖论正在偷窃宝物，所以这个问题需要你来回答。 【名词解释】 长度为 $n$ 的排列$^\texttt{[1]}$：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如，$\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。 子数组$^\texttt{[2]}$：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。对于数组 $a$，我们用 $[l,r]$ 表示由 $a_l,a_{l+1}\dots,a_r$ 组成的子数组。官方中文

输入格式

第一行输入一个整数 $n\left(2\le n\le 2\times 10^5\right)$，表示敌人的数量。 第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n\left(1\le p_i\le n\right)$，表示敌人从左往右的实力。官方中文

输出格式

输出一个整数，表示满足条件的子数组数量。官方中文

说明

请注意常数因子对程序运行效率的影响。官方中文