D. Pair of Topics

The next lecture in a high school requires two topics to be discussed. The i-th topic is interesting by ai units for the teacher and by bi units for the students.

The pair of topics i and j (i < j) is called good if ai + aj > bi + bj (i.e. it is more interesting for the teacher).

Your task is to find the number of good pairs of topics.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 2⋅105) — the number of topics.

The second line of the input contains n integers a1,a2,…,an (1 ≤ ai ≤ 109), where ai is the interestingness of the i-th topic for the teacher.

The third line of the input contains n integers b1,b2,…,bn (1 ≤ bi ≤ 109), where bi is the interestingness of the i-th topic for the students.

Output

Print one integer — the number of good pairs of topic.

Examples

input

5
4 8 2 6 2
4 5 4 1 3

output

7

input

4
1 3 2 4
1 3 2 4

output

0

Problem solving

题意就是让你选出两个下标i , j,求符合ai + aj > bi + bj 的有多少对。

可以直接让a减去b中下标相等的值,然后从大到小排序。

这样就变成从一个数组中挑选两个数和大于0的问题。

因为只选了两个下标,所以只需要先选一个,另外一个用二分查找就可以了。

#include<bits/stdc++.h>
#define IOS()     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const ll N = 2e5+7;
ll a[N];
ll cmp(ll a,ll b)
{
    return a>b;
}
inline void solve()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++)
    {
        ll x;cin>>x;
        a[i]-=x;
    }
    sort(a,a+n,cmp);
    ll ans = 0;
    for(int i=0;i<n;i++)
    {
        if(a[i]<=0) break;

        int l=i,r=n-1;

        while(l<r)
        {
            int mid = (l+r+1)/2;

            if(a[i]+a[mid]<=0) r=mid-1;
            else l = mid;
        }
        ans += l-i;
    }
    cout<<ans<<endl;

}
int main()
{
    IOS();
    solve();
    return 0;
}

E. Sleeping Schedule

Vova had a pretty weird sleeping schedule. There are h hours in a day. Vova will sleep exactly n times. The ii-th time he will sleep exactly after ai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 00). Each time Vova sleeps exactly one day (in other words, h hours).

Vova thinks that the ii-th sleeping time is good if he starts to sleep between hours l and r inclusive.

Vova can control himself and before the ii-th time can choose between two options: go to sleep after ai hours or after ai − 1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

Input

The first line of the input contains four integers n,h,l and r (1 ≤ n ≤ 2000,3 ≤ h ≤ 2000,0 ≤ l ≤ r < h) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains n integers a1,a2,…,an(1 ≤ ai < h), where ai is the number of hours after which Vova goes to sleep the ii-th time.

Output

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.

Example

input

7 24 21 23
16 17 14 20 20 11 22

output

3

Problem solving

题意是说规定一天有h小时,每次睡觉都可以控制睡ai或者ai-1小时,经过n次后最多有多少次醒来的时间在 [l, r] 区间内。

DP 待补!


一个好奇的人