Some Complex Formulas

You are given an integer $n$ and an array $a_1,a_2,\dots ,a_n$ consisting of $n$ integers.

The subarray of the array $a$ beginning at $i$ and ending at $j$ is a segment of numbers $a_i,a_{i+1},\dots ,a_j$. Let this subarray be nice if

That is, if the greatest common divisor of numbers $a_i,a_{i+1},\dots ,a_j$ equals their arithmetic mean.

Your task is to find the number of different pairs of integers $(i,j)$ $(1\le i\le j\le n)$ such that subarray $a_i,a_{i+1},\dots ,a_j$ is nice. Also, you need to find the maximum length of a nice subarray of $a$.

Input

The first line contains one integer $n$ $(1\le n\le 10^5)$ — the number of elements in the array $a$.

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^9)$ — the elements of the array.

Output

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.

Examples

Note

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(a_1)=a_1=\frac{a_1}{1}$.

Subarray $(2,3)$ is not nice because $GCD(a_2,a_3)=GCD(3,2)=1\ne \frac{a_2+a_3}{2}=\frac{3+2}{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$.

Scoring

1. ($36$ points): $n\le 200$;

2. ($64$ points): $n\le 2000$;

3. ($100$ points): no additional constraints.