W SEATST jest $N$ studentów. Każdy student reprezentuje dokładnie jeden kraj. Po zakończeniu zawodów wszyscy studenci uzyskali różne wyniki.

Prabowo przygotowuje tablicę wyników na oficjalną stronę internetową. Dla każdego studenta tablica zawiera jego kraj, wynik, rangę globalną oraz rangę w kraju.

• Ranga globalna studenta jest zdefiniowana jako liczba studentów z wynikiem wyższym od niego.
• Ranga w kraju studenta jest zdefiniowana jako liczba studentów z tego samego kraju z wynikiem wyższym od niego.

Przykład tablicy wyników przedstawiono poniżej:

Zauważ, że zarówno rangi globalne, jak i rangi w kraju zaczynają się od $0$ i żadne rangi nie są pomijane (zarówno globalnie, jak i w obrębie kraju).

Jednakże, podczas publikowania tablicy wyników w Internecie, Prabowo zapomniał zamieścić kraje i wyniki studentów. Dla każdego studenta podano jedynie jego rangę globalną oraz rangę w kraju.

Prabowo próbuje naprawić sytuację i zlecił Ci pomoc w obliczeniu dwóch wielkości:

• liczby par różnych studentów, którzy muszą należeć do tego samego kraju, ORAZ
• liczby par różnych studentów, którzy muszą należeć do różnych krajów.

Ostrzeżenie: Jeśli istnieją dwa przypisania studentów do krajów spełniające rangi globalne i rangi w kraju, w których dwaj studenci należą do tego samego kraju w jednym przypisaniu i do dwóch różnych krajów w drugim, to taka para studentów nie może być liczona w żadnej z tych wielkości.

Pomóż Prabowo!

Szczegóły implementacji

Powinieneś zaimplementować następujące dwie procedury:

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$: Liczba studentów.
• country_rank: Tablica o długości $N$ reprezentująca rangi w kraju. country_rank[i] to ranga w kraju studenta, którego ranga globalna wynosi $i$, dla wszystkich $0 \le i \le N - 1$.

Pierwsza procedura powinna zwrócić liczbę nieuporządkowanych par różnych studentów takich, że we wszystkich przypisaniach studentów do krajów zgodnych z tablicą wyników, studenci w parze należą do tego samego kraju.

Druga procedura powinna zwrócić liczbę nieuporządkowanych par różnych studentów takich, że we wszystkich przypisaniach studentów do krajów zgodnych z tablicą wyników, studenci w parze nie należą do tego samego kraju.

Obie procedury zostaną wywołane co najwyżej raz w każdym przypadku testowym.

Ograniczenia

• $1 \le N \le 1\,000\,000$.
• Istnieje przypisanie studentów do krajów, które spełnia country_rank.

Podzadania

Dla pierwszych 6 podzadań wywołana zostanie tylko procedura count_same_country.

1. ($3$ punkty) $N \leq 8$.
2. ($6$ punktów) country_rank zawiera $0$ co najwyżej dwa razy.
3. ($6$ punktów) country_rank nie zawiera $2$.
4. ($3$ punkty) $N \leq 300$.
5. ($3$ punkty) $N \leq 2000$.
6. ($9$ punktów) Brak dodatkowych ograniczeń.

Dla ostatnich 6 podzadań wywołana zostanie tylko procedura count_diff_country.

1. ($7$ punktów) $N \leq 8$.
2. ($14$ punktów) country_rank zawiera $0$ co najwyżej dwa razy.
3. ($14$ punktów) country_rank nie zawiera $2$.
4. ($7$ punktów) $N \leq 300$.
5. ($7$ punktów) $N \leq 2000$.
6. ($21$ punktów) Brak dodatkowych ograniczeń.

Przykład

Wejście 1

9 same
0 0 1 0 2 1 3 2 1

Wyjście 1

4

Uwagi

Załóżmy, że studenci $0$, $1$ i $3$ reprezentują odpowiednio kraje Singapur, Malezja i Indonezja. Istnieją $4$ pary studentów, którzy zawsze muszą należeć do tego samego kraju: $(2, 4)$, $(2, 6)$, $(4, 6)$ oraz $(5, 7)$.

Wejście 2

9 diff
0 0 1 0 2 1 3 2 1

Wyjście 2

17

Wejście 3

5 same
0 1 0 1 2

Wyjście 3

2

Wejście 4

5 diff
0 1 0 1 2

Wyjście 4

4

Sprawdzacz (Sample Grader)

Format wejścia:

N X
C[0] C[1] ... C[N-1]

gdzie X jest ciągiem znaków same lub diff, co oznacza, że wywoływana jest funkcja count_X_country, a C[i] reprezentuje country_rank[i] dla wszystkich $0 \leq i \leq N - 1$.

Format wyjścia:

Pojedyncza liczba całkowita reprezentująca wynik funkcji count_X_country.