89. 新兵教育

0 Judge

Code: 0


題目敘述

英雄協會裡面有個不成文個規定:先入行的高等英雄會給後入行的低等英雄來一堂新兵教育。協會裡面有$n$個英雄,按照入會的順序,他們的強度依序為$s_1, s_2, ..., s_n$且每個英雄的強度均不同。其中強度最高者排名為$1$,強度最低者排名$n$,以此類推。根據協會潛規則,剛先入行的英雄比後入行的英雄排名超過$k$,他才有新兵教育的資格(i.e. 先入行的英雄排名$r_i$,後入行的$r_j$,當$r_j - r_i > k$ 才可以新兵教育)。當英雄$i$可以新兵教育英雄$j$,我們說$(i,j)$為一個「教育組合」。給定$s_1, s_2, ..., s_n$,求總共有多少個教育組合?

輸入

第一行為正整數$n, k, (1 \leq k \leq n \leq 10^6)$,為英雄數量。

第二行有$n$個正整數$s_1, s_2, ..., s_n$,如題目敘述所示。英雄強度$\leq 10^9$且沒有兩個英雄有相同強度。

輸出

請輸出教育組合的數量並換行。

範例輸入

6 3
7 1 2 9 4 8

範例輸出

0

測資限制

  • 保證$20\%$的測資,$n \leq 1000$
  • 剩下$80\%$無特殊限制

Judge Setting

run-time limit: 2000 ms
memory limit: 256000000 byte
測資數量: 6