#P18522. Mirrors

Mirrors

Mirrors

给定一个长度为 nn 的正整数序列 h1,h2,…,hnh_1,h_2,\ldots,h_n。求满足以下全部条件的整数二元组 (u,v)(u,v) 的数量:

  • 1≤u<v≤n1\le u<v\le n。
  • 存在一个正实数 LL,以及一个长度为 v−u+1v-u+1 的序列 ru,ru+1,…,rvr_u,r_{u+1},\ldots,r_v,满足:对每个 u≤i≤vu\le i\le v,令 hi′=2L−hih'_i=2L-h_i,则 ri∈{hi,hi′}r_i\in\{h_i,h'_i\};并且对每个 u≤i<vu\le i<v,均有 ri<ri+1r_i<r_{i+1}。

特别地,如果 hi=hi′h_i=h'_i,则该位置只有 ri=hir_i=h_i 这一种取值。反射后的高度可以为负数,题目只要求水位 LL 为正实数;所有位置使用同一个 LL。每个待计数的二元组可以各自选择自己的 LL 和反射方式。

输入格式

第一行一个正整数 nn(2≤n≤5×1052\le n\le5\times10^5),表示柱子的数量。

第二行 nn 个正整数 h1,h2,…,hnh_1,h_2,\ldots,h_n(1≤hi≤10121\le h_i\le10^{12}),表示柱子的高度。

本题只有一组输入。

输出格式

输出一行一个整数,表示满足条件的二元组 (u,v)(u,v) 的数量。

原样例

输入:

4
1 3 2 4

输出:

6

答案可能超过 32 位有符号整数范围。