Algorithm Class - Algorithm Runtime 4

Time limit1sMemory limit512 MB

Summary

For a given n, count how many times the inner statement of a nested double loop runs, and report the polynomial degree of that count.

Level: Easy2 of 10
Topics: Math, Combinatorics, Implementation, Brute force
Solved: No attempts yet

Problem

Seojun is working as a teaching assistant for the algorithm runtime class again today. Let us check through a problem whether the students understood what his father taught in class.

Given the input size n, print the runtime of the MenOfPassion algorithm in the same format as the sample output.

The MenOfPassion algorithm is as follows.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # code1
    return sum;
}

Input

The first line gives the input size n (1 ≤ n ≤ 500,000).

Output

On the first line, print the number of times code1 is executed.

On the second line, print the degree of the leading term when the number of times code1 is executed is expressed as a polynomial. If it cannot be expressed as a polynomial or the degree of the leading term is greater than 3, print 4.

Examples1

Example 1
Input
```
7
```
Expected output
```
21
2
```