SEATSTには $N$ 人の学生がいます。各学生はちょうど1つの国を代表しています。コンテスト終了後、すべての学生は異なるスコアを獲得しました。

Prabowoは公式ウェブサイトにリーダーボードを掲載しようとしています。リーダーボードには、各学生について、国、スコア、グローバル順位、および国別順位が記載されます。

• 学生のグローバル順位は、その学生よりも高いスコアを持つ学生の数として定義されます。
• 学生の国別順位は、同じ国の中でその学生よりも高いスコアを持つ学生の数として定義されます。

リーダーボードの例を以下に示します。

グローバル順位と国別順位はどちらも $0$ から始まり、順位の欠番はない（グローバルでも国別でも同様）ことに注意してください。

しかし、リーダーボードがオンラインで公開された際、Prabowoは学生の国とスコアを掲載し忘れてしまいました。各学生について、与えられているのはグローバル順位と国別順位のみです。

Prabowoはこの状況を打開しようとしており、あなたに以下の2つの量を計算するよう依頼しました。

• 同じ国に属さなければならない異なる学生のペアの数、および
• 異なる国に属さなければならない異なる学生のペアの数。

警告 もし、グローバル順位と国別順位を満たす学生の国への割り当てが2通り存在し、一方の割り当てでは2人の学生が同じ国に属し、もう一方の割り当てでは異なる国に属する場合、そのペアはどちらの量にもカウントしてはなりません。

Prabowoを助けてください！

実装の詳細

以下の2つの手続きを実装してください。

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$）。

最初の手続きは、リーダーボードと整合するすべての国への割り当てにおいて、そのペアの学生が同じ国に属するような、異なる学生の非順序ペアの数を返す必要があります。

2番目の手続きは、リーダーボードと整合するすべての国への割り当てにおいて、そのペアの学生が同じ国に属さないような、異なる学生の非順序ペアの数を返す必要があります。

各テストケースにおいて、両方の手続きは最大で1回ずつ呼び出されます。

制約

• $1 \le N \le 1\,000\,000$
• country_rank を満たす学生の国への割り当てが存在する。

小課題

最初の6つの小課題では、count_same_country のみが呼び出されます。

1. ($3$ 点) $N \leq 8$
2. ($6$ 点) country_rank に $0$ が含まれる回数は最大2回。
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$ が含まれる回数は最大2回。
3. ($14$ 点) country_rank に $2$ は含まれない。
4. ($7$ 点) $N \leq 300$
5. ($7$ 点) $N \leq 2000$
6. ($21$ 点) 追加の制約なし。

入出力例

以下の手続き呼び出しを考えます。

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

便宜上、グローバル順位を学生のインデックスとします。学生 $0, 1, 3$ がそれぞれシンガポール、マレーシア、インドネシアを代表していると仮定します。

このとき、この順位が生成され得るすべての可能性を以下の表に示します。

常に同じ国に属さなければならない学生のペアは $(2, 4), (2, 6), (4, 6), (5, 7)$ の $4$ つです。したがって、この手続きは $4$ を返す必要があります。

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

常に異なる国に属さなければならない学生のペアは $(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$ つです。したがって、この手続きは $17$ を返す必要があります。

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

常に同じ国に属さなければならない学生のペアは $(0, 1)$ と $(2, 3)$ の $2$ つです。したがって、この手続きは $2$ を返す必要があります。

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

常に異なる国に属さなければならない学生のペアは $(0, 2), (0, 3), (1, 2), (1, 3)$ の $4$ つです。したがって、この手続きは $4$ を返す必要があります。

サンプルグレーダー

入力形式:

N X

ここで X は文字列 same または diff であり、呼び出される関数が count_X_country であることを示します。また、すべての $0 \leq i \leq N - 1$ について C[i] が country_rank[i] を表します。

出力形式:

count_X_country の出力を表す単一の整数。