QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8218. 水镜

Statistics

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

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

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

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

  • 泉水精灵只能栖息在石柱顶端,或者石柱的像的顶端。用二元组 $(u,r_u)$ 表示泉水精灵在石柱 $u$ 处高度为 $r_u$ 的位置。其中 $r_u$ 只有 $h_u,h'_u$ 两种可能取值。
  • 泉水精灵每次只能前往右侧相邻的石柱(或石柱的像)。
  • 在移动过程中,泉水精灵的高度必须严格单调递增

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

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

形式化的:给定一个长度为 $n$ 的整数序列 $h_1,h_2,\dots,h_n$,求满足以下所有条件的二元组 $(u, v)$ 的数量:

  • $1 \le u < v \le n$,且 $u, v$ 为整数;
  • 存在一个正实数 $L$ 以及一个长度为 $(v-u+1)$ 的序列 $r_u, r_{u+1}, \cdots, r_{v}$ 满足以下所有条件:
    • $\forall u \le i \le v$,记 $h'_i = 2L-h_i$,则 $r_i \in \{h_i, h'_i\}$;
      • 特别地,当 $h_i = h'_i$ 时,$r_i = h_i$;
    • $\forall u \le i < v, r_i < r_{i+1}$。

输入格式

从标准输入读入数据。

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

第二行包含 $n$ 个正整数 $h_1,h_2,\dots,h_n$,表示石柱的高度。

输出格式

输出到标准输出。

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

样例1输入

4
1 3 2 4

样例1输出

6

样例1解释

所有 $\binom{4}{2}=6$ 种 $(u,v)$​ 都是可行的。

对于 $u=1, v=4$,可以选择 $L=2.5$​,则序列 $h'$ 为 $\{4,2,3,1\}$,取序列 $r$ 为 $\{1,2,3,4\}$​​ 可以满足所有条件。

子任务

对于所有测试点,$2 \le n \le 5\times 10 ^ 5$,$1 \le h_i \le 10 ^ {12}$。

子任务编号 $n \leq$ 分值
$1$ $10$ $7$
$2$ $100$ $10$
$3$ $4\,000$ $18$
$4$ $10^5$ $30$
$5$ $5 \times 10^5$ $35$