SVALUE - Siêu giá trị
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nxphuc

An là một người rất thích toán học và rất thích sự mày mò sáng tạo. Cậu nghĩ ra một bài toán như sau: cho một mảng gồm N phần tử, mỗi phần tử có một giá trị Ai. An định nghĩa Siêu giá trị của một mảng là tổng chênh lệch của các cặp phần tử nhân với giá trị lớn nhất của mảng. Nhưng vì giá trị này có thể rất lớn, nên An định nghĩa thêm một khái niệm khác là Siêu giá trị tương đương, Siêu giá trị tương đương là đồng dư không âm nhỏ nhất của Siêu giá trị với 109+7

Ví dụ:

 - Mảng gồm 2 phần tử {1, 2}. Chỉ có 1 cặp phần tử là (1, 2), tổng chênh lệch của các cặp là 1, giá trị lớn nhất của mảng là 2. Siêu giá trị của mảng là 1*2 = 2. Siêu giá trị tương đương của nó cũng bằng 2.

 - Mảng gồm 5 phần tử: {4, 3, 1, 5, 2}. Các cặp phần tử tương ứng là (4, 3), (4, 1), (4, 5), (4, 2), (3, 1), (3, 5), (3, 2), (1, 5), (1, 2) và (5, 2). Tổng chênh lệch: 1 + 3 + 1 + 2 + 2 + 2 + 1 + 4 + 1 + 3 = 20. Giá trị lớn nhất của mảng là 5 nên Siêu giá trị và Siêu giá trị tương đương của mảng là 100.

An rất đắc chí với bài toán này và cậu ta thách đố ngay với Phú - người bạn thân nhất của cậu ta. Nhưng Phú lại không phải là người giỏi toán cho lắm. Bạn hãy giúp Phú giải quyết bài toán này nhé.

Dữ liệu nhập: Dòng đầu chứa một số nguyên dương N - số lượng phần tử của mảng (2 ≤ N ≤ 105). Dòng thứ hai chứa N số nguyên là các phần tử của mảng (0 ≤ Ai ≤ 109).

Dữ liệu xuất: Một số nguyên duy nhất là Siêu giá trị tương đương của mảng đã cho.

Ví dụ

  • input
    2
    1 2
    output
    2
  • input
    5
    4 5 3 1 2
    output
    100
Back to Top