Submission #2245619

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

const int mod = 1e9 + 7;

int n, A[N*2], L[N*2], R[N*2], S[N*2];

signed main(){
  
  cin>>n;
  
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    A[a]++;
  }
  
  for(int i=1;i<N;i++) L[i] = L[i-1] + A[i];
  
  for(int i=N-2;i>=0;i--) R[i] = R[i+1] + A[i];
  
  for(int i=1;i<N;i++)
    if( A[i] ) S[i] = R[ i * 2 ] * A[i];
  
  for(int i=N-2;i>=0;i--){
    S[i] += S[i+1];
    S[i] %= mod;
  }
  
  int ans = 0;
  
  for(int i=1;i<N;i++){
    
    ans += ( L[ i / 2 ] * A[i] % mod ) * ( S[ i * 2 ] % mod );
    
    ans %= mod;
  }
  
  cout<<ans<<endl;
  
  return 0;
}

Submission Info

Judge Result