AT_ttpc2024_1_k Sum is One

$ 0 $ と $ 1 $ からなる長さ $ N $ の数列 $ A = (A_1, A_2, \dots, A_N) $ が与えられます。 $ \frac{N (N - 1)}{2} $ 頂点の単純無向グラフ $ G = (V, E) $ を以下のように定義します。 - $ 1

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ ここで、 $ \text{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

各テストケースに対し、答えを出力せよ。

### 部分点 以下の制約を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 - $ 1 \leq T \leq 1000 $ - $ 3 \leq N \leq 5000 $ - $ 1 $ つの入力の中のテストケースすべてにわたる $ N $ の総和は $ 5000 $ 以下 ### Sample Explanation 1 $ 1 $ 個目のテストケースについて、連結成分は以下の $ 4 $ つです。 - $ \lbrace (1,2),(2,3),(2,4),(2,5),(3,4),(4,5) \rbrace $ - $ \lbrace (1,3),(3,5) \rbrace $ - $ \lbrace (1,4) \rbrace $ - $ \lbrace (1,5) \rbrace $ $ 2 $ 個目のテストケースについて、グラフに辺は張られないため連結成分の個数は $ 10 $ です。 ### Constraints - 入力はすべて整数 - $ 1 \leq T \leq {10}^5 $ - $ 3 \leq N \leq {10}^6 $ - $ A_i $ は $ 0 $ または $ 1 $ ( $ 1 \leq i \leq N $ ) - $ 1 $ つの入力の中のテストケースすべてにわたる $ N $ の総和は $ {10}^6 $ 以下