Description:

There are N n points on a coordinate axis OX. The I − Th i-th I −th point is located at The integer point x I xi xi and has a speed v i vi vi. It is guaranteed that no two points occupy the same coordinate. All n points move with the constant speed, The coordinate of the I − T h i-th I −th point at the moment t t t (T can be non-integer) is calculated as x I + t ⋅ V I ⋅ ⋅ vi xi xi + t + t vi.

Consider two points i i i and j j j. Let d ( i , j ) d(i,j) 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 ) d(i,j) d(i,j) will be 0.

Your task is to calculate the value ∑ 1 ≤ I < j ≤ n d (I, J) \ Sum_ {1≤ I <j≤ N} D (I,j) ∑1≤ I <j≤nd(I,j) (the sum of minimum distances over all points).

Input

⋅105) N (2≤ N ≤2⋅10^5) n(2≤n≤2⋅105) — The number of points.

The second line of The input contains n n n integers x 1, x 2, ,x n (1 ≤ x I ≤ 1 0 8) x_1,x_2… , x_n (1 x_i 10 ^ 8 or less) or less x1, x2,… Xn (1≤ XI ≤108), where XI is the initial coordinate of the I-th point. It is guaranteed that all XI are distinct.

The third line of The input contains n n n integers V 1, V 2… ,v n (− 1 0 8 ≤ v I ≤ 1 0 8) v_1,v_2… , v_n (8-10 ^ vi or less 10 ^ 8 or less) v1, v2,… ,vn(−108≤vi≤108), where v I v_i vi is the speed of the I −th i-th I −th point.

Output

Print one integer — the value ∑ 1 ≤ I < j ≤ n d (I, J) \ Sum_ {1≤ I <j≤ N} D (I,j) ∑1≤ I <j≤nd(I,j) (the sum of minimum distances over all points).

Examples

input

3
1 3 2
- 100. 2 3
Copy the code

output

3
Copy the code

input

5
2 1 4 3 5
2 2 2 3 4
Copy the code

output

19
Copy the code

input

2
2 1
- 3 0
Copy the code

output

0
Copy the code

Answer:

Given n, n, n points with their initial positions x, x, x, and their moving velocity v, V, v, ask what is the sum of the minima of all pairs of points at any time, not the same time but the sum of the minima of each pair of points, any number of times.

Time can be any real number, and for any two points, if x I <=xj x_i<=x_j xi<=xj, and x I <= V j x_i<=v_j xi<=vj, then I, j I, j I, j can never meet. Otherwise we can definitely meet, so we only need to calculate the case where x I <=xj x_i<= X_j xi<=xj, and x I <=vj x_i<=v_j xi<=vj. In this case, the contribution is the distance, and the tree maintains a sum.

AC code:

const int N = 2e5 + 10;
ll c[N][2], b[N], ans, len; // The two-dimensional array 0 maintains several smaller ones, and 1 calculates the prefix sum
int n;

struct node
{
    int x;
    int v;
} a[N];

bool cmp(node a, node b)
{
    return a.x < b.x;
}

void add(int x, int val)
{
    while (x <= n)
        c[x][0]++, c[x][1] += val, x += lowbit(x);
}

ll ask(int x, int k)
{
    ll res = 0;
    while (x)
        res += c[x][k], x -= lowbit(x);
    return res;
}

int main(a)
{
    sd(n);
    ans = 0, len = 0;
    rep(i, 1, n)
        sd(a[i].x);
    rep(i, 1, n)
    {
        sd(a[i].v);
        b[i] = a[i].v;
    }
    sort(a + 1, a + 1 + n, cmp);
    sort(b + 1, b + 1 + n);
    len = unique(b + 1, b + 1 + n) - b - 1; // Do not repeat the number of elements
    rep(i, 1, n)
    {
        int now = lower_bound(b + 1, b + 1 + len, a[i].v) - b; // Find the contribution of the position further than a[I] and the speed is greater than a[I]
        ans += a[i].x * ask(now, 0) - ask(now, 1);
        //ask(now, 0) how many positions are smaller than x,
        //ask(now, 1) ask(now, 1) ask(now, 1) ask(now, 1)
        add(now, a[i].x);        
    }
    pld(ans);
    return 0;
}
Copy the code