CF1805F2.Survival of the Weakest (hard version)
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
This is the hard version of the problem. It differs from the easy one only in constraints on n . You can make hacks only if you lock both versions.
Let a1,a2,…,an be an array of non-negative integers. Let F(a1,a2,…,an) be the sorted in the non-decreasing order array of n−1 smallest numbers of the form ai+aj , where 1≤i<j≤n . In other words, F(a1,a2,…,an) is the sorted in the non-decreasing order array of n−1 smallest sums of all possible pairs of elements of the array a1,a2,…,an . For example, F(1,2,5,7)=[1+2,1+5,2+5]=[3,6,7] .
You are given an array of non-negative integers a1,a2,…,an . Determine the single element of the array n−1F(F(F…F(a1,a2,…,an)…)) . Since the answer can be quite large, output it modulo 109+7 .
输入格式
The first line contains one integer n ( 2≤n≤2⋅105 ) — the initial length of the array.
The second line contains n integers a1,a2,…,an ( 0≤ai≤109 ) — the array elements.
输出格式
Output a single number — the answer modulo 109+7 .
输入输出样例
输入#1
5 1 2 4 5 6
输出#1
34
输入#2
9 1 1 1 7 7 7 9 9 9
输出#2
256
输入#3
7 1 7 9 2 0 0 9
输出#3
20
输入#4
3 1000000000 1000000000 777
输出#4
1540
说明/提示
In the first test, the array is transformed as follows: [1,2,4,5,6]→[3,5,6,6]→[8,9,9]→[17,17]→[34] . The only element of the final array is 34 .
In the second test, F(a1,a2,…,an) is [2,2,2,8,8,8,8,8] . This array is made up of 3 numbers of the form 1+1 and 5 numbers of the form 1+7 .
In the fourth test, the array is transformed as follows: [109,109,777]→[109+777,109+777]→[2⋅109+1554] . 2⋅109+1554 modulo 109+7 equals 1540 .