#602알고리즘 수행 횟수 6

입력의 크기 n이 주어질 때, 아래 알고리즘에서 코드1이 실행되는 횟수와, 이 횟수를 다항식으로 나타냈을 때 최고차항의 차수를 출력하는 프로그램을 작성하시오.

CountOp(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k];  # 코드1
    return sum;
}

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어집니다.

첫째 줄에 코드1 의 수행 횟수를 출력합니다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력합니다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력합니다.