Il y a $N$ étudiants à SEATST. Chaque étudiant représente exactement un pays. Après le concours, tous les étudiants ont obtenu des scores différents.

Prabowo est sur le point de publier le classement sur le site officiel. Pour chaque étudiant, le classement indique son pays, son score, son rang mondial et son rang national.

• Le rang mondial d'un étudiant est défini comme le nombre d'étudiants ayant un score supérieur au sien.
• Le rang national d'un étudiant est défini comme le nombre d'étudiants du même pays ayant un score supérieur au sien.

Un exemple de classement est présenté ci-dessous :

Notez que les rangs mondiaux et les rangs nationaux commencent tous deux à $0$, et qu'aucun rang n'est sauté (que ce soit au niveau mondial ou au sein d'un pays).

Cependant, lors de la mise en ligne du classement, Prabowo a oublié de publier les pays et les scores des étudiants. Pour chaque étudiant, nous ne connaissons que son rang mondial et son rang au sein de son pays.

Prabowo tente de sauver la situation et vous a chargé de l'aider à calculer deux quantités :

• le nombre de paires d'étudiants distincts qui doivent appartenir au même pays, ET
• le nombre de paires d'étudiants distincts qui doivent appartenir à des pays différents.

Avertissement S'il existe deux attributions d'étudiants aux pays qui satisfont les rangs mondiaux et les rangs nationaux, où deux étudiants appartiennent au même pays dans une attribution et à deux pays différents dans l'autre, alors cette paire d'étudiants ne doit être comptée dans aucune des deux quantités.

Aidez Prabowo !

Détails d'implémentation

Vous devez implémenter les deux procédures suivantes.

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$ : Le nombre d'étudiants.
• country_rank : Un tableau de longueur $N$ représentant les rangs nationaux. country_rank[i] est le rang national de l'étudiant dont le rang mondial est $i$, pour tout $0 \le i \le N - 1$.

La première procédure doit renvoyer le nombre de paires non ordonnées d'étudiants distincts tels que, dans toutes les attributions d'étudiants aux pays cohérentes avec le classement, les étudiants de la paire appartiennent au même pays.

La seconde procédure doit renvoyer le nombre de paires non ordonnées d'étudiants distincts tels que, dans toutes les attributions d'étudiants aux pays cohérentes avec le classement, les étudiants de la paire n'appartiennent pas au même pays.

Chaque procédure sera appelée au plus une fois par cas de test.

Contraintes

• $1 \le N \le 1\,000\,000$.
• Il existe une attribution d'étudiants aux pays qui satisfait country_rank.

Sous-tâches

Pour les 6 premières sous-tâches, seule count_same_country sera appelée.

1. ($3$ points) $N \leq 8$.
2. ($6$ points) country_rank contient $0$ au plus deux fois.
3. ($6$ points) country_rank ne contient pas $2$.
4. ($3$ points) $N \leq 300$.
5. ($3$ points) $N \leq 2000$.
6. ($9$ points) Aucune contrainte supplémentaire.

Pour les 6 dernières sous-tâches, seule count_diff_country sera appelée.

1. ($7$ points) $N \leq 8$.
2. ($14$ points) country_rank contient $0$ au plus deux fois.
3. ($14$ points) country_rank ne contient pas $2$.
4. ($7$ points) $N \leq 300$.
5. ($7$ points) $N \leq 2000$.
6. ($21$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

4

Remarque

Supposons que les étudiants $0$, $1$ et $3$ représentent les pays Singapour, Malaisie et Indonésie, respectivement. Le tableau suivant liste toutes les manières possibles dont ce classement aurait pu être produit :

Il y a $4$ paires d'étudiants qui doivent toujours appartenir au même pays : $(2, 4)$, $(2, 6)$, $(4,6)$ et $(5, 7)$.

Entrée 2

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

Sortie 2

17

Entrée 3

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

Sortie 3

2

Entrée 4

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

Sortie 4

4

Évaluateur d'exemple

Format d'entrée :

N X

où X est soit la chaîne same, soit diff, de sorte que l'appel de fonction effectué soit count_X_country et C[i] représente country_rank[i], pour tout $0 \leq i \leq N - 1$.

Format de sortie :

Un entier unique représentant le résultat de count_X_country.