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.
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$$$.
A non-negative integer in a single line indicating the number of the intervals with duplicates.
42 3 4 6
3
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.
