CPU usage time limit is 1 second

Runtime memory usage limit is 256 megabytes

You are given an integer $n$ and an array $a_{1},a_{2},…,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},…,a_{j}$. Let this subarray be nice if

$GCD(a_{i},a_{i+1},…,a_{j})=j−i+1∑_{k=i}a_{k} $

That is, if the greatest common divisor of numbers $a_{i},a_{i+1},…,a_{j}$ 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 $a_{i},a_{i+1},…,a_{j}$ 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≤10_{5})$ — the number of elements in the array $a$.

The second line contains $n$ integers $a_{1},a_{2},…,a_{n}$ $(1≤a_{i}≤10_{9})$ — 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.

Input

Answer

Input #1

Answer #1

Input #2

Answer #2

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}=1a_{1} $.

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