Array

题号：NC14614
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

Given an array A with length n a[1],a[2],...,a[n] where a[i] (1<=i<=n) is positive integer.

Count the number of pair (l,r) such that a[l],a[l+1],...,a[r] can be rearranged to form a geometric sequence.

Geometric sequence is an array where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. i.e. A = [1,2,4,8,16] is a geometric sequence.

输入描述:

The first line is an integer n (1 <= n <= 100000).
The second line consists of n integer a[1],a[2],...,a[n] where a[i] <= 100000 for 1<=i<=n.

输出描述:

An integer answer for the problem.

示例1

输入

复制

5
1 1 2 4 1

输出

复制

说明

The 11 pairs of (l,r) are (1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5).

示例2

输入

复制

10
3 1 1 1 5 2 2 5 3 3

输出

复制

备注:

The answer can be quite large that you may use long long in C++ or the similar in other languages.