Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Insertion Sort

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array *a* of size *n* in the non-decreasing order.

for (int i = 1; i < n; i = i + 1)

{

int j = i;

while (j > 0 && a[j] < a[j - 1])

{

swap(a[j], a[j - 1]); // swap elements a[j] and a[j - 1]

j = j - 1;

}

}

Petya uses this algorithm only for sorting of arrays that are permutations of numbers from 0 to *n* - 1. He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.

It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.

Input

The first line contains a single integer *n* (2 ≤ *n* ≤ 5000) — the length of the permutation. The second line contains *n* different integers from 0 to *n* - 1, inclusive — the actual permutation.

Output

Print two integers: the minimum number of times the swap function is executed and the number of such pairs (*i*, *j*) that swapping the elements of the input permutation with indexes *i* and *j* leads to the minimum number of the executions.

Examples

Input

5

4 0 3 1 2

Output

3 2

Input

5

1 2 3 4 0

Output

3 4

Note

In the first sample the appropriate pairs are (0, 3) and (0, 4).

In the second sample the appropriate pairs are (0, 4), (1, 4), (2, 4) and (3, 4).

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 16:20:22 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|