# HackerRank Coolguy and Two Subsequences problem solution

In this HackerRank Coolguy and Two Subsequences problem solution, you are given a 1-indexed array that contains N elements. we need to find the answer after implementing and executing pseudocode and then print the answer using the given expression.

## Problem solution in Python programming.

```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
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)
ans += A[i] * (pairs - oldpairs)
return ans % (10**9 + 7)

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

## Problem solution in Java Programming.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

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;
}
}```

## Problem solution in C++ programming.

```#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
const int mod = 1000000007;

const int N = (1 << 17);
pii t[2*N];
const int INF = 2e9;

pii combine (const pii & a, const pii & b) {
if (a.first < b.first)
return a;
if (b.first < a.first)
return b;
return make_pair (a.first, a.second + b.second);
}

void build (const vi & a, int v, int tl, int tr) {
if (tl == tr) {
t[v] = make_pair (a[tl], 1);
} else {
int tm = (tl + tr) / 2;
build (a, v*2, tl, tm);
build (a, v*2+1, tm+1, tr);
t[v] = combine (t[v*2], t[v*2+1]);
}
}

pii get_min (int v, int tl, int tr, int l, int r) {
if (l > r)
return make_pair (INF, 0);
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return combine (get_min (v*2, tl, tm, l, min(r,tm)),
get_min (v*2+1, tm+1, tr, max(l,tm+1), r));
}

void update (int v, int tl, int tr, int pos, int new_val) {
if (tl == tr)
t[v] = make_pair (new_val, 1);
else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update (v*2, tl, tm, pos, new_val);
else
update (v*2+1, tm+1, tr, pos, new_val);
t[v] = combine (t[v*2], t[v*2+1]);
}
}

ll c2(ll x) {
return x*(x-1)/2%mod;
}

int inv3 = (mod+1)/3;
ll c3(ll x) {
return c2(x)*(x-2)%mod*inv3%mod;
}

int main() {
int n;
cin >> n;
vi a(n);
vii ts(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
ts[i] = pii(a[i], i);
}
sort(ts.begin(), ts.end());
/*  for (int i = 0; i < n; ++i) {
a[ts[i].second] = i;
}*/
set<int> x;
x.insert(-1);
x.insert(n);
ll sum = c2(n + 1), res = 0;
for (int i = 0; i < n; ++i) {
int pos = ts[i].second;
auto it = x.lower_bound(pos);
int r = *it; --it;
int l = *it;
sum = (sum - c2(r - l)) % mod;
int l1 = pos - l, l2 = r - pos;
ll cnt = (sum*l1%mod*l2 + l1*c3(l2+1) + l2*c3(l1+1)) % mod;
res = (res + ts[i].first*cnt) % mod;
//    cerr << pos << ' ' << l1 << ' ' << l2 << ' ' << sum << ' ' << res << endl;
x.insert(pos);
sum = (sum + c2(l1) + c2(l2)) % mod;
}
cout << (res + mod) % mod << endl;
return 0;
}```

## Problem solution in C programming.

```#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;
}```