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$ 的陣列，代表國家排名。對於所有 $0 \le i \le N - 1$，country_rank[i] 是全球排名為 $i$ 的學生的國家排名。

第一個程序應回傳滿足以下條件的無序學生對數：在所有符合排行榜的學生國家分配中，該對學生皆屬於同一個國家。

第二個程序應回傳滿足以下條件的無序學生對數：在所有符合排行榜的學生國家分配中，該對學生皆不屬於同一個國家。

每個測試案例中，這兩個程序最多各會被呼叫一次。

資料範圍

• $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

9 same
0 0 1 0 2 1 3 2 1

輸出格式 1

4

說明

假設學生 $0$、$1$ 和 $3$（此處為方便起見，按全球排名索引學生）分別代表新加坡、馬來西亞和印尼。下表列出了此排名可能產生的所有方式：

有 $4$ 對學生必須始終屬於同一個國家：$(2, 4)$、$(2, 6)$、$(4, 6)$ 和 $(5, 7)$。

輸入格式 2

9 diff
0 0 1 0 2 1 3 2 1

輸出格式 2

17

輸入格式 3

5 same
0 1 0 1 2

輸出格式 3

2

輸入格式 4

5 diff
0 1 0 1 2

輸出格式 4

4

範例評測程式

輸入格式：

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

其中 X 為字串 same 或 diff，表示正在呼叫的函式為 count_X_country，且對於所有 $0 \le i \le N - 1$，C[i] 代表 country_rank[i]。

輸出格式：

一個代表 count_X_country 輸出的整數。