You are given an integer n and an array a1,a2,…,an consisting of n integers.
The subarray of the array a beginning at i and ending at j is a segment of numbers ai,ai+1,…,aj. Let this subarray be nice if
That is, if the greatest common divisor of numbers ai,ai+1,…,aj equals their arithmetic mean.
Your task is to find the number of different pairs of integers (i,j) (1≤i≤j≤n) such that subarray ai,ai+1,…,aj is nice. Also, you need to find the maximum length of a nice subarray of a.
The first line contains one integer n (1≤n≤105) — the number of elements in the array a.
The second line contains n integers a1,a2,…,an (1≤ai≤109) — the elements of the array.
In the only line, you need to output the number of nice subarrays of the array a and the length of the longest such subarray.
In the first example, there are 6 subarrays in total: (1,1), (1,2), (1,3), (2,2), (2,3) and (3,3).
Subarray (1,1) is nice because GCD(a1)=a1=1a1.
Subarray (2,3) is not nice because GCD(a2,a3)=GCD(3,2)=1=2a2+a3=23+2=2.5.
There are exactly 3 nice subarrays in this array: (1,1), (2,2), (3,3) and all these subarrays have lengths of 1.
(36 points): n≤200;
(64 points): n≤2000;
(100 points): no additional constraints.