Positive Pairs

2 secs 1024 MB
magurofly's icon magurofly

問題文

NN 個の整数 A1,,ANA_1, \ldots, A_N が与えられます。 1i<jN1 \le i \lt j \le N となるすべての (i,j)(i, j) に対して、 max(0,AiAj)\max(0, A_i A_j) の総和を 109+710^9 + 7 で割ったあまりを出力してください。

制約

  • 1N2×1051 \le N \le 2 \times 10^5
  • Ai109|A_i| \le 10^9
  • 入力はすべて整数

入力

NA1  ANN\\ A_1\ \ldots\ A_N\\

出力

答えを一行に出力してください。

入出力例

入力例1

3
1 2 3

出力例1

11

1×2+1×3+2×3=111 \times 2 + 1 \times 3 + 2 \times 3 = 11 となります。

入力例2

3
-1 1 2

出力例2

2

1,2,2-1, -2, 2 のうち正であるのは 22 だけです。

入力例3

2
100000 100000

出力例3

999999937

109+710^9+7 で割ったあまりを出力してください。

Submit


Go (1.21)