SEATST에는 $N$명의 학생이 있습니다. 각 학생은 정확히 하나의 국가를 대표합니다. 대회 후, 모든 학생은 서로 다른 점수를 받았습니다.

Prabowo는 공식 웹사이트에 순위표를 게시하려고 합니다. 순위표에는 각 학생의 국가, 점수, 전체 순위, 국가 내 순위가 나열됩니다.

• 학생의 전체 순위는 해당 학생보다 높은 점수를 받은 학생의 수로 정의됩니다.
• 학생의 국가 내 순위는 같은 국가 내에서 해당 학생보다 높은 점수를 받은 학생의 수로 정의됩니다.

순위표의 예시는 다음과 같습니다.

전체 순위와 국가 내 순위 모두 $0$부터 시작하며, 순위가 건너뛰어지지 않음(전체적으로든 국가 내에서든)을 확인하십시오.

하지만 순위표가 온라인에 업로드될 때, Prabowo는 학생들의 국가와 점수를 게시하는 것을 잊었습니다. 각 학생에 대해 우리는 전체 순위와 국가 내 순위만을 알고 있습니다.

Prabowo는 이 상황을 해결하기 위해 다음 두 가지 값을 계산하는 작업을 여러분에게 맡겼습니다.

• 반드시 같은 국가에 속해야 하는 서로 다른 학생 쌍의 수, 그리고
• 반드시 다른 국가에 속해야 하는 서로 다른 학생 쌍의 수.

경고 전체 순위와 국가 내 순위를 만족하는 학생들의 국가 배정 방식이 두 가지 존재할 때, 한 배정 방식에서는 두 학생이 같은 국가에 속하고 다른 배정 방식에서는 서로 다른 국가에 속한다면, 이 학생 쌍은 어느 쪽 수량에도 포함되어서는 안 됩니다.

Prabowo를 도와주세요!

구현 세부사항

다음 두 프로시저를 구현해야 합니다.

long long count_same_country(int N, std::vector<int> country_rank)
long long count_diff_country(int N, std::vector<int> country_rank)

• $N$: 학생 수.
• country_rank: 국가 내 순위를 나타내는 길이 $N$의 배열. country_rank[i]는 전체 순위가 $i$인 학생의 국가 내 순위입니다 ($0 \le i \le N - 1$).

첫 번째 프로시저는 순위표와 일치하는 모든 국가 배정 방식에서 항상 같은 국가에 속하는 서로 다른 학생들의 순서 없는 쌍의 수를 반환해야 합니다.

두 번째 프로시저는 순위표와 일치하는 모든 국가 배정 방식에서 항상 서로 다른 국가에 속하는 서로 다른 학생들의 순서 없는 쌍의 수를 반환해야 합니다.

각 테스트 케이스에서 두 프로시저는 최대 한 번씩 호출됩니다.

제한

• $1 \le N \le 1\,000\,000$.
• country_rank를 만족하는 학생들의 국가 배정 방식이 존재합니다.

서브태스크

처음 6개의 서브태스크에서는 count_same_country만 호출됩니다.

1. ($3$점) $N \leq 8$.
2. ($6$점) country_rank에 $0$이 최대 두 번 포함됨.
3. ($6$점) country_rank에 $2$가 포함되지 않음.
4. ($3$점) $N \leq 300$.
5. ($3$점) $N \leq 2000$.
6. ($9$점) 추가 제한 없음.

마지막 6개의 서브태스크에서는 count_diff_country만 호출됩니다.

1. ($7$점) $N \leq 8$.
2. ($14$점) country_rank에 $0$이 최대 두 번 포함됨.
3. ($14$점) country_rank에 $2$가 포함되지 않음.
4. ($7$점) $N \leq 300$.
5. ($7$점) $N \leq 2000$.
6. ($21$점) 추가 제한 없음.

예제

입력 1

count_same_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

출력 1

4

참고

편의상 학생들을 전체 순위로 인덱싱한다고 가정할 때, 학생 $0$, $1$, $3$이 각각 싱가포르, 말레이시아, 인도네시아를 대표한다고 가정해 봅시다.

그러면 다음 표는 이 순위가 생성될 수 있었던 모든 가능한 방법을 나열합니다.

항상 같은 국가에 속해야 하는 학생 쌍은 $(2, 4)$, $(2, 6)$, $(4, 6)$, $(5, 7)$로 총 $4$쌍이 존재합니다. 따라서 이 프로시저는 $4$를 반환해야 합니다.

입력 2

count_diff_country(9, [0, 0, 1, 0, 2, 1, 3, 2, 1])

출력 2

17

참고

항상 서로 다른 국가에 속해야 하는 학생 쌍은 $(0, 1)$, $(0, 3)$, $(1, 3)$, $(2, 3)$, $(2, 5)$, $(2, 7)$, $(2, 8)$, $(3, 4)$, $(3, 6)$, $(4, 5)$, $(4, 7)$, $(4, 8)$, $(5, 6)$, $(5, 8)$, $(6, 7)$, $(6, 8)$, $(7, 8)$로 총 $17$쌍이 존재합니다. 따라서 이 프로시저는 $17$을 반환해야 합니다.

입력 3

count_same_country(5, [0, 1, 0, 1, 2])

출력 3

2

참고

항상 같은 국가에 속해야 하는 학생 쌍은 $(0, 1)$과 $(2, 3)$으로 총 $2$쌍이 존재합니다. 따라서 이 프로시저는 $2$를 반환해야 합니다.

입력 4

count_diff_country(5, [0, 1, 0, 1, 2])

출력 4

4

참고

항상 서로 다른 국가에 속해야 하는 학생 쌍은 $(0, 2)$, $(0, 3)$, $(1, 2)$, $(1, 3)$으로 총 $4$쌍이 존재합니다. 따라서 이 프로시저는 $4$를 반환해야 합니다.

샘플 채점기

입력 형식:

N X

여기서 X는 same 또는 diff이며, 각각 count_same_country 또는 count_diff_country 함수가 호출됨을 의미합니다. C[i]는 모든 $0 \le i \le N - 1$에 대해 country_rank[i]를 나타냅니다.

출력 형식:

count_X_country의 결과값을 나타내는 정수 하나를 출력합니다.