Migrated from Lutece 2928 转生为lsr只能度过不如黎酱的人生

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：gcd的性质，链表/map
黎酱是一名成绩优异的高中生，人长得帅而且还有女朋友。他和女朋友两人非常恩爱，他们几乎每天都要一起约会。但是他的班主任章鱼拳老师对此颇有微词，经常设法刁难黎酱。

某个周五，章鱼拳老师为了让黎酱安心呆在学校学习，给班上布置了一道很麻烦的题，并且要求做完才放学。可是黎酱依然很快解决了这道题，章鱼拳老师无可奈何只能放黎酱离开。

可是lsr——黎酱的同班同学——却头疼了，这道题对lsr来说似乎相当棘手。

为了早点回家摆烂，lsr希望能尽快解决这道题：

给定一个长度为$n$的序列$a_i$。对于所有满足$1\le l\le r\le n$的整数$l,r$，求$gcd(l,r)$的不同取值个数，并对于每一种可能的取值$x$，求出有多少个符合条件的有序数对$(l,r)$使得$gcd(l,r)=x$。其中，$gcd(l,r)$是指$a_l,a_{l+1},...,a_{r-1},a_r$共$r-l+1$个整数的最大公约数。

你能帮帮可怜的lsr吗？

Input

第一行包含一个整数$n$，表示序列长度。
第二行包含$n$个整数，第$i$个整数表示$a_i$。

Output

输出第一行包含一个整数$m$，表示$gcd(l,r)$可能的不同取值个数。
接下来输出$m$行，其中的第$i$行包含两个整数$b_i$和$c_i$(用空格隔开)，$b_i$表示$gcd(l,r)$的一种可能取值，$c_i$表示有$c_i$个符合条件的有序数对$(l,r)$使得$gcd(l,r)=b_i$。
要求这$m$行按$b_i$升序排列后输出。

Samples

10
4 6 4 3 9 27 4 8 2 1

8
1 37
2 6
3 3
4 4
6 1
8 1
9 2
27 1

Constraints

$1\le n\le 3*10^5,1\le a_i\le 10^9$

Note

黎酱的提示：求a和b的最大公因数，可以用辗转相除法，也可以用algorithm库中的__gcd(a,b)函数。

Resources

2023 UESTC ICPC Training for Data Structures