Hay $N$ estudiantes en SEATST. Cada estudiante representa exactamente a un país. Después del concurso, todos los estudiantes obtuvieron puntuaciones diferentes.

Prabowo está a punto de publicar la tabla de clasificación en el sitio web oficial. Para cada estudiante, la tabla de clasificación enumera su país, puntuación, rango global y rango en el país.

• El rango global de un estudiante se define como el número de estudiantes con una puntuación mayor a la suya.
• El rango en el país de un estudiante se define como el número de estudiantes dentro del mismo país con una puntuación mayor a la suya.

A continuación se muestra un ejemplo de una tabla de clasificación:

Observe que tanto los rangos globales como los rangos en el país comienzan desde $0$, y no se omiten rangos (ya sea globalmente o dentro de un país).

Sin embargo, cuando se subió la tabla de clasificación en línea, Prabowo olvidó publicar los países y las puntuaciones de los estudiantes. Para cada estudiante, solo se nos da su rango global y su rango dentro de su país.

Prabowo está tratando de salvar la situación y le ha encargado ayudarle a calcular dos cantidades:

• el número de pares de estudiantes distintos que deben pertenecer al mismo país, Y
• el número de pares de estudiantes distintos que deben pertenecer a diferentes países.

Advertencia: Si existen dos asignaciones de estudiantes a países que satisfacen los rangos globales y los rangos en el país, donde dos estudiantes pertenecen al mismo país en una asignación y a dos países diferentes en la otra, entonces este par de estudiantes no debe contarse en ninguna de las dos cantidades.

¡Por favor, ayude a Prabowo!

Detalles de implementación

Debe implementar los siguientes dos procedimientos.

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$: El número de estudiantes.
• country_rank: Un arreglo de longitud $N$ que representa los rangos en el país. country_rank[i] es el rango en el país del estudiante cuyo rango global es $i$, para todo $0 \le i \le N - 1$.

El primer procedimiento debe devolver el número de pares no ordenados de estudiantes distintos tales que, en todas las asignaciones de estudiantes a países consistentes con la tabla de clasificación, los estudiantes del par pertenezcan al mismo país.

El segundo procedimiento debe devolver el número de pares no ordenados de estudiantes distintos tales que, en todas las asignaciones de estudiantes a países consistentes con la tabla de clasificación, los estudiantes del par no pertenezcan al mismo país.

Ambos procedimientos serán llamados como máximo una vez en cada caso de prueba.

Restricciones

• $1 \le N \le 1\,000\,000$.
• Existe una asignación de estudiantes a países que satisface country_rank.

Subtareas

Para las primeras 6 subtareas, solo se llamará a count_same_country.

1. ($3$ puntos) $N \leq 8$.
2. ($6$ puntos) country_rank contiene $0$ como máximo dos veces.
3. ($6$ puntos) country_rank no contiene $2$.
4. ($3$ puntos) $N \leq 300$.
5. ($3$ puntos) $N \leq 2000$.
6. ($9$ puntos) Sin restricciones adicionales.

Para las últimas 6 subtareas, solo se llamará a count_diff_country.

1. ($7$ puntos) $N \leq 8$.
2. ($14$ puntos) country_rank contiene $0$ como máximo dos veces.
3. ($14$ puntos) country_rank no contiene $2$.
4. ($7$ puntos) $N \leq 300$.
5. ($7$ puntos) $N \leq 2000$.
6. ($21$ puntos) Sin restricciones adicionales.

Ejemplos

Entrada 1

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

Salida 1

4

Entrada 2

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

Salida 2

17

Entrada 3

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

Salida 3

2

Entrada 4

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

Salida 4

4

Evaluador de muestra

Formato de entrada:

N X

donde X es la cadena same o diff, de modo que la llamada a la función que se realiza es count_X_country y C[i] representa country_rank[i], para todo $0 \leq i \leq N - 1$.

Formato de salida:

Un solo número entero que representa la salida de count_X_country.