Coolguy and Two Subsequences

                            Solution in C :

In   C++ :







#define _CRT_SECURE_NO_WARNINGS

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk
#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash

#define eps 1e-9
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

const int N = 1000500;


const double INF = 1e18;

using namespace std;

int n;
int ar[N];

int brute()
{
	int ans = 0;

	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			for (int q = j + 1; q < n; q++)
			{
				for (int w = q; w < n; w++)
				{
					int mn = 1e9;
					for (int a = i; a <= j; a++)
					{
						mn = min(mn, ar[a]);
					}
					for (int a = q; a <= w; a++)
					{
						mn = min(mn, ar[a]);
					}
					ans += mn;
					ans %= bs;
				}
			}
		}
	}
	return ans;
}

vector<pair<int, pair<int, int> > > events;
int block[N];

set<int> ban;
long long ttl;

int get_prev(int x)
{
	set<int>::iterator it;
	it = ban.lower_bound(x);
	--it;
	return *it;
}

int get_next(int x)
{
	set<int>::iterator it;
	it = ban.lower_bound(x);
	return *it;
}

long long TTL;

long long C(long long x)
{
	return x*(x + 1) / 2 % bs;
}

void remove_segment(int l, int r)
{
	TTL -= C(r - l - 1);
}

void add_segment(int l, int r)
{
	TTL += C(r - l - 1);
}

int smart()
{
	long long ans = 0;

	events.clear();

	for (int i = 0; i < n; i++)
	{
		events.push_back(make_pair(ar[i], make_pair(1, i)));
	}
	
	sort(events.begin(), events.end());

	ban.clear();
	ban.insert(-1);
	ban.insert(n);

	TTL = C(n);
	TTL %= bs;

	for (int i = 0; i < events.size(); i++)
	{
		int ps = events[i].second.second;
		int l, r;
		l = get_prev(ps);
		r = get_next(ps);
		int span = r - l - 1;
		long long val1 = TTL - C(span) + bs;
		val1 %= bs;
		ans += 1ll * val1*(ps - l) % bs*(r - ps) % bs*ar[ps]%bs;
		ans %= bs;
		//cout << ps << " " << l << " " << r << " "<<ar[ps]<<" "<<ans<<endl;

		for (int Q = l + 1; Q <= ps; Q++)
		{
			ans += C(Q - l - 1)*(r - ps)%bs*ar[ps]%bs;
			ans %= bs;
		}
		for (int Q = ps; Q < r; Q++)
		{
			ans += C(r - Q - 1)*(ps - l)%bs*ar[ps]%bs;
			ans %= bs;
		}
		
		remove_segment(l, r);
		add_segment(l, ps);
		add_segment(ps, r);
		ban.insert(ps);

	}

	return ans;
}

int main(){
	//freopen("route.in","r",stdin);
	//freopen("route.out","w",stdout);
	//freopen("F:/in.txt", "r", stdin);
	//freopen("F:/output.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

//	srand(10);

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> ar[i];
	//	ar[i] = rand() % 5;
	}

//	cout << brute() << endl;
	cout << smart() << endl;

	cin.get(); cin.get();
	return 0;
}









In   Java :






import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class CoolguyAndTwoSubsequences {
final static int constant = 1000000007;

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();

final int[] A = new int[N];
int[] l = new int[N];
int[] r = new int[N];

boolean[] mark = new boolean[N];
Integer[] index = new Integer[N];

for (int i = 0; i < N; i++) {
A[i] = scanner.nextInt();
l[i] = r[i] = i;
mark[i] = false;
index[i] = Integer.valueOf(i);
}
Arrays.sort(index, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return A[o2] - A[o1];
}
});
long res = 0;
long dp = 0;
for (int i = 0; i < N; i++) {
int ptr = index[i];
mark[ptr] = true;
int left = 0;
int right = 0;
if (ptr > 0 && mark[ptr - 1]) {
left = ptr - l[ptr - 1];
dp = (dp + constant - fun1(left)) % constant;
}
if (ptr < N - 1 && mark[ptr + 1]) {
right = r[ptr + 1] - ptr;
dp = (dp + constant - fun1(right)) % constant;
}
l[ptr + right] = ptr - left;
r[ptr - left] = ptr + right;

long c = 0;

c += (right + 1) * fun2(left) % constant;
c %= constant;

c += (left + 1) * fun2(right) % constant;
c %= constant;

c += (left + 1L) * (right + 1L) % constant * dp % constant;
c %= constant;

res += c * A[ptr] % constant;
res %= constant;
dp += fun1(left + right + 1);
dp %= constant;
}
System.out.println(res);
scanner.close();
}

private static long fun2(long p) {
return p * (p + 1) * (p + 2) / 6 % constant;
}

private static long fun1(long p) {
return p * (p + 1) / 2 % constant;
}
}







In   C   :







#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,
int*b,int*left_b,int*right_b,
int left_size, int right_size);
int a[200000],idx[200000],a_idx[200000],
st[200000],left[200000],right[200000];
long long dp[200001];

int main(){
int N,sp,i,j;
long long sum=0,ans=0,A,B;
dp[0]=0;
for(i=1;i<=200000;i++)
dp[i]=(dp[i-1]+i*(long long)(i+1)/2)%MOD;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",a+i);
idx[i]=i;
}
if(N==1){
printf("0");
return 0;
}
sort_a2(a,idx,N);
for(i=0;i<N;i++)
a_idx[idx[i]]=i;
for(i=sp=0;i<N;i++){
while(sp && a_idx[st[sp-1]]>a_idx[i])
sp--;
if(!sp)
left[i]=-1;
else
left[i]=st[sp-1];
st[sp++]=i;
}
for(i=N-1,sp=0;i>=0;i--){
while(sp && a_idx[st[sp-1]]>a_idx[i])
sp--;
if(!sp)
right[i]=N;
else
right[i]=st[sp-1];
st[sp++]=i;
}
for(i=N-1;i>=0;i--){
j=idx[i];
A=(right[j]-j)*(long long)(j-left[j])%MOD;
sum=(sum-(right[j]-j-1)*(long long)(right[j]-j)/2%MOD-(j-left[j]-1)*(long long)(j-left[j])/2%MOD+2*MOD)%MOD;
B=A*sum%MOD;
B=(B+dp[right[j]-j-1]*(j-left[j]))%MOD;
B=(B+dp[j-left[j]-1]*(right[j]-j))%MOD;
ans=(ans+B*a[i])%MOD;
sum=(sum+(right[j]-left[j]-1)*(long long)(right[j]-left[j])/2)%MOD;
}
printf("%lld",ans);
return 0;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,
int*right_a,int*b,int*left_b,
int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}









In   Python3  :






def smart():
    left = [0] * (n + 2)
    right = [0] * (n + 2)
    singles = pairs = 0
    ans = 0
    def remove(k):
        nonlocal singles, pairs
        s = k * (k + 1) // 2
        singles -= s
        pairs -= (k+2)*(k+1)*k*(k-1)//24 + s * singles
    def add(k):
        nonlocal singles, pairs
        s = k * (k + 1) // 2
        pairs += (k+2)*(k+1)*k*(k-1)//24 + s * singles
        singles += s
    for i in sorted(range(1, n+1), key=A.__getitem__)[::-1]:
        l, r = left[i-1], right[i+1]
        k = l + 1 + r
        right[i - l] = left[i + r] = k
        oldpairs = pairs
        remove(l)
        remove(r)
        add(k)
        ans += A[i] * (pairs - oldpairs)
    return ans % (10**9 + 7)

n = int(input())
A = [None] + list(map(int, input().split()))
print(smart())