В SEATST учатся $N$ студентов. Каждый студент представляет ровно одну страну. После соревнования все студенты получили различные баллы.

Прабаво собирается опубликовать таблицу лидеров на официальном сайте. Для каждого студента в таблице указаны страна, балл, глобальный ранг и ранг внутри страны.

• Глобальный ранг студента определяется как количество студентов, набравших больше баллов, чем он.
• Ранг внутри страны студента определяется как количество студентов из той же страны, набравших больше баллов, чем он.

Пример таблицы лидеров приведен ниже:

Заметим, что как глобальные ранги, так и ранги внутри страны начинаются с $0$, и никакие ранги не пропускаются (ни в глобальном зачете, ни внутри страны).

Однако при публикации таблицы в интернете Прабаво забыл указать страны и баллы студентов. Для каждого студента нам даны только его глобальный ранг и его ранг внутри страны.

Прабаво пытается исправить ситуацию и просит вас помочь вычислить две величины:

• количество пар различных студентов, которые обязаны принадлежать к одной и той же стране, И
• количество пар различных студентов, которые обязаны принадлежать к разным странам.

Предупреждение: Если существуют два способа распределения студентов по странам, удовлетворяющие данным глобальным рангам и рангам внутри страны, при которых в одном случае два студента принадлежат к одной стране, а в другом — к разным, то такая пара студентов не должна учитываться ни в одной из величин.

Помогите Прабаво!

Детали реализации

Вам необходимо реализовать следующие две процедуры:

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$ (для удобства будем индексировать студентов по их глобальному рангу) представляют страны Сингапур, Малайзия и Индонезия соответственно.

В следующей таблице приведены все возможные способы распределения, которые могли бы привести к такому ранжированию:

Существует $4$ пары студентов, которые всегда обязаны принадлежать к одной и той же стране: $(2, 4)$, $(2, 6)$, $(4, 6)$ и $(5, 7)$. Таким образом, процедура должна вернуть $4$.

Входные данные 2

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

Выходные данные 2

17

Примечание

Существует $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$.

Входные данные 3

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

Выходные данные 3

2

Примечание

Существует $2$ пары студентов, которые всегда обязаны принадлежать к одной и той же стране: $(0, 1)$ и $(2, 3)$. Таким образом, процедура должна вернуть $2$.

Входные данные 4

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

Выходные данные 4

4

Примечание

Существует $4$ пары студентов, которые всегда обязаны принадлежать к разным странам: $(0, 2)$, $(0, 3)$, $(1, 2)$, $(1, 3)$. Таким образом, процедура должна вернуть $4$.

Примеры использования проверяющей программы

Формат входных данных:

N X

где X — это строка same или diff, означающая, что вызывается функция count_X_country, а C[i] представляет country_rank[i] для всех $0 \leq i \leq N - 1$.

Формат выходных данных:

Одно целое число, представляющее результат работы count_X_country.