Mirrors
给定一个长度为 n 的正整数序列 h1,h2,…,hn。求满足以下全部条件的整数二元组 (u,v) 的数量:
- 1≤u<v≤n。
- 存在一个正实数 L,以及一个长度为 v−u+1 的序列 ru,ru+1,…,rv,满足:对每个 u≤i≤v,令 hi′=2L−hi,则 ri∈{hi,hi′};并且对每个 u≤i<v,均有 ri<ri+1。
特别地,如果 hi=hi′,则该位置只有 ri=hi 这一种取值。反射后的高度可以为负数,题目只要求水位 L 为正实数;所有位置使用同一个 L。每个待计数的二元组可以各自选择自己的 L 和反射方式。
输入格式
第一行一个正整数 n(2≤n≤5×105),表示柱子的数量。
第二行 n 个正整数 h1,h2,…,hn(1≤hi≤1012),表示柱子的高度。
本题只有一组输入。
输出格式
输出一行一个整数,表示满足条件的二元组 (u,v) 的数量。
原样例
输入:
4
1 3 2 4
输出:
6
答案可能超过 32 位有符号整数范围。