# Summing Pieces

### Problem Statement :

```Consider an array, A, of length n. We can split A into contiguous segments called pieces and store them as another array, B. For example, if A = [1,2,3], we have the following arrays of pieces:

B = [(1),(2),(3)] contains three 1-element pieces.
B = [(1,2),(3)] contains two pieces, one having 2 elements and the other having 1 element.
B = [(1),(2,3)] contains two pieces, one having 1 element and the other having 2 elements.
B = [(1,2,3)] contains one 3-element piece.
We consider the value of a piece in some array B to be (sum of all numbers in the piece) * (length of piece), and we consider the total value of some array B to be the sum of the values for all pieces in that B. For example, the total value of B = [1,2,4),(5,1),(2)] is (1+2+4)*3+(5+1)*2+(2)*1 = 35.

Given A, find the total values for all possible B's, sum them together, and print this sum modulo (10^9 +  7) on a new line.

Input Format

The first line contains a single integer, n, denoting the size of array A.
The second line contains n space-separated integers describing the respective values in A (i.e.,a0,a1,...,an-1).

Constraints
1 <= n <= 10^6
1 <= ai <= 10^9

Output Format

Print a single integer denoting the sum of the total values for all piece arrays (B's) of A, modulo (10^9 + 7).```

### Solution :

```                            ```Solution in C :

In C++ :

//It’s never too late to become what you might have been....
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 1000001

ll power[maxn],sub[maxn],pre[maxn],suff[maxn],a[maxn];

ll ways(ll x)
{
if(x==0)
return 1;
return power[x-1];
}
int main()
{
boost1;boost2;
ll i,j,n,q,x,y,sum=0,ans=0;
power=1;
for(i=1;i<=1000000;i++)
power[i]=(2*power[i-1])%mod;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
sum%=mod;
}
for(i=1;i<=n;i++)
pre[i]=(pre[i-1]+a[i])%mod;
for(i=n;i>=1;i--)
suff[i]=(suff[i+1]+a[i])%mod;

sub=sum;
for(i=2;i<=n;i++)
{
sub[i]=sub[i-1];
sub[i]=(sub[i]+suff[i])%mod;
sub[i]=(sub[i]-suff[n-i+2]+mod)%mod;
}

for(i=1;i<=n-2;i++)
{
x=sub[i];
x=(x-pre[i]+mod)%mod;
x=(x-suff[n-i+1]+mod)%mod;
ans=(ans+(((i*power[n-i-2])%mod)*x)%mod)%mod;
}
for(i=1;i<=n;i++)
ans=(ans+(((i*pre[i])%mod)*ways(n-i))%mod)%mod;
for(i=n;i>1;i--)
ans=(ans+((((n-i+1)*suff[i])%mod)*ways(i-1))%mod)%mod;
cout<<ans;
return 0;
}

In Java :

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

public class Solution {

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

int n = in.nextInt();
long sum = 0;
long[] powers2 = new long[n+1];
powers2 = 1;
for(int i=1; i<=n; i++)
powers2[i] = (powers2[i-1] << 1) % 1000000007;

for(int i=1; i<=n; i++){
long left = ((powers2[i] - 1) * powers2[n-i]) % 1000000007;
long right = ((powers2[1+n-i]-1) * powers2[i-1]) % 1000000007;
long v = left + right - powers2[n-1];
sum = (sum + (v * in.nextLong())) % 1000000007;
}

System.out.println(sum);

}
}

In C :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef long long int LL;

#define din(n) scanf("%d",&n)
#define dout(n) printf("%d\n",n)
#define llin(n) scanf("%lld",&n)
#define llout(n) printf("%lld\n",n)
#define strin(n) scanf(" %s",n)
#define strout(n) printf("%s\n",n)

int arr;
int dp;
int m = 1e9 + 7;
int mod=1e9+7;

int mult(int a,int b)
{
LL tmp = (LL)a*(LL)b ;
tmp = tmp%m;
return (int)tmp;
}

{
LL tmp = (LL)a + (LL)b;
tmp = tmp%m;
return (int)tmp;
}

int max(int a, int b)
{
if(a>b) return a; return b;
}

long long po(int x, int y)
{
int pro=1;
while(y>0)
{
if(mod==1)
return(0);
else if(y&1 != 0)
pro = mult(pro, x);
x = mult(x,x);
y=y>>1;
}
return pro;
}

int main()
{
int n; din(n);
for(int i=0;i<n;i++)
{
din(arr[i]);
}
dp = po(2,n) - 1;
dp[n-1] = po(2,n) - 1;
int len1 = n-2, len2 = 0;
for(int i=1;i<=n/2;i++)
{
dp[i] = add(dp[i-1], (po(2, len1--)-po(2,len2++))%m ); // mod
dp[n-i-1] = dp[i];
}
int ans = 0;
for(int i=0;i<n;i++)
{
//printf("%d ", dp[i]);
}
//printf("\n");
dout(ans);
return(0);
}

In Python3 :

import math

n = int(input())
A = list(map(int,input().split()))
T = *n
MOD = 10**9 +7

def pow_mod(x, y):
number = 1
while y:
if y & 1:
number = number * x % MOD
y >>= 1
x = x * x % MOD
return number

mem = pow_mod(2,n) + pow_mod(2,n-1)
ans = 0
k = 0
for i in range(1,math.ceil(n/2)+1):
temp = mem - pow_mod(2,n-i) - pow_mod(2,i-1)
T[i-1] = temp
T[n-i] = temp

# print(T)

for a in A:
# print(k)
ans = (ans + T[k]*a)%MOD
k+=1

print(ans)```
```

## Tree Coordinates

We consider metric space to be a pair, , where is a set and such that the following conditions hold: where is the distance between points and . Let's define the product of two metric spaces, , to be such that: , where , . So, it follows logically that is also a metric space. We then define squared metric space, , to be the product of a metric space multiplied with itself: . For

## Array Pairs

Consider an array of n integers, A = [ a1, a2, . . . . an] . Find and print the total number of (i , j) pairs such that ai * aj <= max(ai, ai+1, . . . aj) where i < j. Input Format The first line contains an integer, n , denoting the number of elements in the array. The second line consists of n space-separated integers describing the respective values of a1, a2 , . . . an .

## Self Balancing Tree

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. We define balance factor for each node as : balanceFactor = height(left subtree) - height(righ

## Array and simple queries

Given two numbers N and M. N indicates the number of elements in the array A[](1-indexed) and M indicates number of queries. You need to perform two types of queries on the array A[] . You are given queries. Queries can be of two types, type 1 and type 2. Type 1 queries are represented as 1 i j : Modify the given array by removing elements from i to j and adding them to the front. Ty