#P10144. [WC2024] 水镜

[WC2024] 水镜

题目描述

提示:我们在题目描述的最后提供了一份简要的、形式化描述的题面。

A 城是一座多雨的城市,山溪泉水众多。出于对水的喜爱,市民们在城市中央修建了一座大喷泉。

喷泉的水池中有一排 nn 个石柱,从左到右编号为 1,2,,n1, 2, \cdots , n,第 ii 个石柱的高度为 hih_i。水池中有储水,水位 LL 为一个正实数。第 ii 个石柱会产生一个高度为 hi=2Lhih'_i = 2L - h_i 的像。若石柱在水面上方,像在水面下方;若石柱在水面下方,像在水面上方;若石柱顶端与水面重合,则像也与水面重合。

传说水中栖息着泉水精灵,每到满月之夜,它们就会在石柱上起舞,行动规则如下:

  • 泉水精灵只能栖息在石柱顶端,或者石柱的像的顶端。即如果泉水精灵在石柱 uu 上,它的高度 rur_u 便只有 hu,huh_u, h'_u 两种可能取值。
  • 泉水精灵每次只能前往右侧相邻的石柱(或石柱的像)。
  • 在移动过程中,泉水精灵的高度必须严格单调递增

泉水精灵会选择一个石柱(或石柱的像)为起点,进行若干次移动后停止。这样的过程称为一次舞蹈

A 城的雨季漫长,由于不规律的降雨,喷泉的水位可能会多次变化,舞蹈路径的可能性也随之改变。作为远道而来的旅人,你很想知道有多少种舞蹈是可能实现的。具体地,你需要计算有多少对 (u,v)(u, v)1u<vn1 ≤ u < v ≤ n),满足存在一种水位 LL,使得泉水精灵在一次舞蹈中,能从第 uu 个石柱(或它的像)出发,到达第 vv 个石柱(或它的像)。

形式化的:给定一个长度为 nn 的正整数序列 h1,h2,,hnh_1, h_2,\cdots , h_n,求满足以下所有条件的 二元组 (u,v)(u, v) 的数量:

  • 1u<vn1 \le u < v \le n,且 u,vu, v 为整数;
  • 存在一个正实数 LL 以及一个长度为 (vu+1)(v - u + 1) 的序列 ru,ru+1,,rvr_u, r_{u+1},\cdots , r_v 满足以下 所有条件:
  • uiv\forall u \le i \le v,记 hi=2Lhih'_i = 2L - h_i,则 ri{hi,hi}r_i \in \{h_i,h'_i\},特别地,当 hi=hih_i = h'_i 时,ri=hir_i = h_i
  • ui<v,ri<ri+1\forall u \le i < v, r_i < r_{i+1}

输入格式

输入的第一行包含一个正整数 nn,表示石柱的个数。

输入的第二行包含 nn 个正整数 h1,h2,,hnh_1, h_2, \cdots , h_n,表示石柱的高度。

输出格式

输出一行一个整数,表示符合题目描述的 (u,v)(u, v) 对数。

4
1 3 2 4
6

提示

样例 1 解释

所有 (42)=6\binom{4}{2}=6(u,v)(u, v) 都是可行的。 对于 u=1,v=4u = 1, v = 4,可以选择 L=2.5L = 2.5,则序列 hh'{4,2,3,1}\{4, 2, 3, 1\},取序列 rr{1,2,3,4}\{1, 2, 3, 4\} 可以满足所有条件。

数据范围

对于所有测试数据:

  • 2n5×1052\le n\le 5\times 10^5
  • 1in,1hi1012\forall 1\le i\le n,1\le h_i\le 10^{12}
测试点编号 nn\le
121\sim 2 1010
343\sim 4 100100
565\sim 6 400400
7117\sim 11 40004000
121312\sim 13 5×1045\times 10^4
141614\sim 16 10510^5
171917\sim 19 2×1052\times 10^5
202520\sim 25 5×1055\times 10^5