Compressing a sequence using a cyclic shift

TypeScript Medium loops

Task «Compressing a sequence using a cyclic shift»

Given a sequence of integers. It is necessary to find the minimum length of a compressed string obtained by cyclically shifting the original sequence and then compressing consecutive identical numbers into the format 'number count'. For example, the sequence [1,1,2,2,2] after compression becomes '1 2 2 3'. A cyclic shift means that we can move several first elements to the end. It is necessary to iterate over all possible shifts (from 0 to n-1), perform compression, and find the minimum length of the resulting string (in characters, including spaces). If the lengths are equal, choose the shift with the smallest index. Constraints: n ≤ 100, numbers from 0 to 100.

Input Format

The first line contains an integer n (1 ≤ n ≤ 100) — the number of values. The second line contains n integers separated by spaces.

Output Format

Output two numbers: the shift number (starting from 0) and the minimum length of the compressed string, separated by a space.

Examples

Example 1

INPUT

3
1 2 3

OUTPUT

0 11

Example 2

INPUT

4
1 1 1 1

OUTPUT

0 3

Example 3

INPUT

6 3
1 -2 3 4 -5 6

OUTPUT

0 25

main.ts