Petya and Array 

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Petya has an array $\mathrm{aa consisting\; of nn integers.\; He\; has\; learned\; partial\; sums\; recently,\; and\; now\; he\; can\; calculate\; the\; sum\; of\; elements\; on\; any\; segment\; of\; the\; array\; really\; fast.\; The\; segment\; is\; a\; non-empty\; sequence\; of\; elements\; standing\; one\; next\; to\; another\; in\; the\; array.}$

Now he wonders what is the number of segments in his array with the sum less than $\mathrm{tt.\; Help\; Petya\; to\; calculate\; this\; number.}$

More formally, you are required to calculate the number of pairs $\mathrm{l,rl,r (l\le rl\le r)\; such\; that al+al+1+\cdots +ar-1+ar<tal+al+1+\cdots +ar-1+ar<t.}$

Input

The first line contains two integers $\mathrm{nn and tt (1\le n\le 200000,|t|\le 2\cdot 10141\le n\le 200000,|t|\le 2\cdot 1014).}$

The second line contains a sequence of integers ${\mathrm{a1,a2,\dots ,ana1,a2,\dots ,an (|ai|\le 109|ai|\le 109)\; —\; the\; description\; of\; Petya\text{'}s\; array.\; Note\; that\; there\; might\; be\; negative,\; zero\; and\; positive\; elements.}}^{}$

Output

Print the number of segments in Petya's array with the sum of elements less than $\mathrm{tt.}$

Examples

input

5 4 5 -1 3 4 -1

output

5

input

3 0 -1 2 -3

output

4

input

4 -1 -2 1 -2 3

output

3

Note

In the first example the following segments have sum less than $\mathrm{44:}$

• $[2,2][2,2],\; sum\; of\; elements\; is -1-1$
• $[2,3][2,3],\; sum\; of\; elements\; is 22$
• $[3,3][3,3],\; sum\; of\; elements\; is 33$
• $[4,5][4,5],\; sum\; of\; elements\; is 33$
• $[5,5][5,5],\; sum\; of\; elements\; is -1$

$参考博客$

　　找区间和小于t的个数，区间和的问题，一般用前缀和来做

　　可以看成sum[i]>t+sum[k]的个数，i<k<=n。这样就变成了一个逆序对的问题

　　

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6 #include
            
              7 #include
             
               8 #include
              
                9 #define maxn 500005 10 #define lson l,mid,rt<<1 11 #define rson mid+1,r,rt<<1|1 12 typedef long long ll; 13 using namespace std; 14 15 vector
               
                v; 16 ll n; 17 ll a[maxn]; 18 ll sum[maxn]; 19 20 int tree[maxn<<3]; 21 22 int getid(ll x){ 23 return lower_bound(v.begin(),v.end(),x)-v.begin()+1; 24 } 25 26 void pushup(int rt){ 27 tree[rt]=tree[rt<<1]+tree[rt<<1|1]; 28 } 29 30 void build(int l,int r,int rt){ 31 if(l==r){ 32 tree[rt]=0; 33 return; 34 } 35 int mid=(l+r)/2; 36 build(lson); 37 build(rson); 38 pushup(rt); 39 } 40 41 void add(int L,int k,int l,int r,int rt){ 42 if(l==r){ 43 tree[rt]+=k; 44 return; 45 } 46 int mid=(l+r)/2; 47 if(L<=mid) add(L,k,lson); 48 else add(L,k,rson); 49 pushup(rt); 50 } 51 52 ll query(int L,int R,int l,int r,int rt){ 53 if(L<=l&&R>=r){ 54 return tree[rt]; 55 } 56 int mid=(l+r)/2; 57 ll ans=0; 58 if(L<=mid) ans+=query(L,R,lson); 59 if(R>mid) ans+=query(L,R,rson); 60 return ans; 61 } 62 63 64 int main(){ 65 66 std::ios::sync_with_stdio(false); 67 ll t; 68 cin>>n>>t; 69 for(int i=1;i<=n;i++){ 70 cin>>a[i]; 71 } 72 v.push_back(t-1); 73 for(int i=1;i<=n;i++){ 74 sum[i]=a[i]+sum[i-1]; 75 v.push_back(sum[i]); 76 v.push_back(sum[i]+t-1); 77 } 78 if(n==1){ 79 if(a[1]
                
                 =1;i--){ 94 ans+=query(1,getid(sum[i]+t-1),1,Size,1); 95 add(getid(sum[i]),1,1,Size,1); 96 } 97 ans+=query(1,getid(t-1),1,Size,1); 98 99 cout<
                 
                  <