Half Gcd Summation

2 secs 1024 MB
sgsw

問題文


自然数と、長さの自然数列が与えられます。

この時、左から2つずつをペアとして、そのうちどちらかを取り出し、長さの自然数列を取り出します。

このような数列の取り出し方は、それぞれのペアでどちらを取るかを考えることで通り考えられますが、その全ての数列に対して、

の総和をで求めてください。

なお、

とします。

入力


N
A_1 A_2 ... A_(2N)

制約


サンプル


入力1
3
1 4 2 7 9 6
出力1
9

この時、個のペアは順にであり、それぞれのペアから1つを取り出すことで作れる、長さの数列は全てで

通りあります。

これらの数列のの値は、順番にであり、これらの合計はになります。

入力2
7
170968102 275508394 3196157 519009647 375950994 861285711 246245660 251125881 652686828 368044278 610971871 267235406 471017707 16164438
出力2
128

このケースでは問題ありませんが、で出力することを忘れないでください。

入力3
1
1 1
出力3
2

この時、数列通りあり、その合計はです。

入力4
4
10 10 10 10 10 10 10 10
出力4
160

提出


Go (1.14)