B. LCM Gifts
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Tomorrow is Xiao Peng's birthday, so Xiao Chang wants to give some gifts to Xiao Peng.

Xiao Chang buys $$$n$$$ gifts from the Internet and arranges them in a row from left to right. Each gift has a positive integer eigenvalue, where the $$$i$$$th gift from left to right has eigenvalue $$$a_i$$$. Since it is a bit scary to give all these gifts in one go, he decides to choose an interval in which to give these gifts to his little friend.

However, Xiao Chang, who is extremely sensitive to duplicates, acutely realizes that there are intervals $$$[l,r]$$$ that are with duplicates! Specifically, if Xiao Chang can select at least two distinct non-empty subsequences (not necessarily consecutive) from the interval $$$[l,r]$$$ such that the Least Common Multiple of every number in these two subsequences is equal to the Least Common Multiple of every number in the interval $$$[l,r]$$$. Formally, for the subscripted full set $$$U = [l,r] \cap \mathbb{Z}$$$, if two non-empty sets $$$S,T$$$ can be found that satisfy $$$S \ne T$$$, $$$S \subseteq U$$$, $$$T \subseteq U$$$, $$$\operatorname{lcm}_{x \in S} a_x = \operatorname{lcm}_{x \in T} a_x = \operatorname{lcm}_{x \in U} a_x$$$, then the interval $$$[l,r]$$$ is said to be with duplicates.

Since it's one day before Xiao Peng's birthday, now, a bored Xiao Chang wants to know how many intervals $$$[l,r]$$$ are with duplicates.

Input

The first line contains one positive integer $$$n$$$, indicating the number of the gifts. It is guaranteed that $$$1 \le n \le 2 \times 10^5$$$.

The second line contains $$$n$$$ positive integers, the $$$i$$$th number $$$a_i$$$ indicating the eigenvalue of the $$$i$$$th gift. It is guaranteed that $$$1 \le a_i \le 10^6$$$.

Output

A non-negative integer in a single line indicating the number of the intervals with duplicates.

Example
Input
4
2 3 4 6
Output
3
Note

Explanation to Sample 1

The intervals of with duplicates are $$$[1,3]$$$, $$$[1,4]$$$, $$$[2,4]$$$ respectively. Take the interval $$$[1,4]$$$ as an example, choose the subscript set $$$S = \{2,3\}$$$, $$$T = \{1,3,4\}$$$, i.e., the subsequences $$$[3,4]$$$ and $$$[2,4,6]$$$ satisfy the condition.