There are $n$ points on a coordinate axis $OX$. The $i$-th point is located at the integer point $x_i$ and has a speed $v_i$. It is guaranteed that no two points occupy the same coordinate. All $n$ points move with the constant speed, the coordinate of the $i$-th point at the moment $t$ ($t$ can be non-integer) is calculated as $x_i + t \cdot v_i$.

Consider two points $i$ and $j$. Let $d(i, j)$ be the minimum possible distance between these two points over any possible moments of time (even non-integer). It means that if two points $i$ and $j$ coincide at some moment, the value $d(i, j)$ will be $0$.

Your task is to calculate the value $\sum\limits_{1 \le i < j \le n}$ $d(i, j)$ (the sum of minimum distances over all pairs of points).


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of points.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^8$), where $x_i$ is the initial coordinate of the $i$-th point. It is guaranteed that all $x_i$ are distinct.

The third line of the input contains $n$ integers $v_1, v_2, \dots, v_n$ ($-10^8 \le v_i \le 10^8$), where $v_i$ is the speed of the $i$-th point.


-----Output-----

Print one integer — the value $\sum\limits_{1 \le i < j \le n}$ $d(i, j)$ (the sum of minimum distances over all pairs of points).


-----Examples-----
Input
3
1 3 2
-100 2 3

Output
3

Input
5
2 1 4 3 5
2 2 2 3 4

Output
19

Input
2
2 1
-3 0

Output
0

Difficulty: introductory

Starter code:

Solutions:

def bitadd(a,w,bit):
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit):
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


n = int(input())

x = list(map(int,input().split()))
v = list(map(int,input().split()))

vlis = []
for i in v:
    vlis.append(i)
vlis.sort()
vdic = {}

for i in range(n):
    vdic[vlis[i]] = i+1
#print (vdic)



xv = []
for i in range(n):
    xv.append([x[i],v[i]])
xv.sort()

ans = 0
BIT = [0] * (n+1)
BIT2 = [0] * (n+1)
for i in range(n):

    x,v = xv[i]

    ans += x * bitsum(vdic[v],BIT2) - bitsum(vdic[v],BIT)
    bitadd(vdic[v] , x , BIT)
    bitadd(vdic[v] , 1 , BIT2)

print (ans)


import math
import bisect

class Fenwick:
    def __init__(self, n):
        self.data = [[0,0] for i in range(n)] 
    
    def update(self, pos, dist):
        while pos<len(self.data):
            self.data[pos][0] += 1
            self.data[pos][1] += dist
            pos = pos | (pos+1)
    
    def query(self, pos):
        ans = [0,0]
        while pos > 0:
            ans[0] += self.data[pos-1][0]
            ans[1] += self.data[pos-1][1]
            pos = pos & (pos-1)
        return ans


def rints():
    return list(map(int,input().split()))


n = int(input())

x = rints()
v = rints()

ascDist = list(range(n))
ascDist.sort(key=lambda i: x[i])

uniqueSpeeds = sorted(list(set(v)))

tree = Fenwick(len(uniqueSpeeds))


ans = 0
for i in ascDist:
    speedId = bisect.bisect_left(uniqueSpeeds, v[i])
    count, dsum = tree.query(speedId+1)
    ans += count*x[i] - dsum
    tree.update(speedId, x[i])

print(ans)



import sys
input = sys.stdin.readline

n=int(input())
X=list(map(int,input().split()))
V=list(map(int,input().split()))

XV=[(X[i],V[i]) for i in range(n)]

#compression_dict_x={a: ind for ind, a in enumerate(sorted(set(X)))}
compression_dict_v={a: ind+2 for ind, a in enumerate(sorted(set(V)))}

XV=[(XV[i][0], compression_dict_v[XV[i][1]]) for i in range(n)]
XV.sort(reverse=True)

LEN=len(compression_dict_v)+3

BIT1=[0]*(LEN+1)

def update1(v,w):
    while v<=LEN:
        BIT1[v]+=w
        v+=(v&(-v))

def getvalue1(v):
    ANS=0
    while v!=0:
        ANS+=BIT1[v]
        v-=(v&(-v))
    return ANS

BIT2=[0]*(LEN+1)

def update2(v,w):
    while v<=LEN:
        BIT2[v]+=w
        v+=(v&(-v))

def getvalue2(v):
    ANS=0
    while v!=0:
        ANS+=BIT2[v]
        v-=(v&(-v))
    return ANS

ANS=0
for x,v in XV:
    ANS+=(getvalue2(LEN)-getvalue2(v-1))-(getvalue1(LEN)-getvalue1(v-1))*x
    #print(getvalue2(LEN),getvalue2(v-1),getvalue1(LEN),getvalue1(v-1))
    #print(x,v,ANS)

    update1(v,1)
    update2(v,x)

print(ANS)