Max - Min của đoạn

View as PDF




Authors:
Problem types
Points: 400 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

algorit là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay algorit đang thắc mắc một bài toán như sau :

Bạn được cung cấp một dãy số gồm \(n\) số nguyên \(A_1,A_2,...,A_n\).

Nhiệm vụ của bạn là đếm số lượng đoạn con có \(max - min = k\). Ở đây \(max\)\(min\) là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.

algorit suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp algorit nhé !

Input

  • Dòng đầu tiên gồm 2 số nguyên \(n,k(0 \le k \le 10^9)\).
  • Dòng thứ 2 gồm \(n\) số nguyên \(A_1,A_2,A_3,...,A_n(-10^9 \le A_i \le 10^9)\).

Output

  • Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^5\).
  • Subtask \(3\) (\(30\%\) số điểm): \(n \le 5 \times 10^5\).

Example

Test 1

Input
5 2
1 2 1 3 3
Output
6

Comments


  • 0
    hien18086    3:03 a.m. 25 feb, 2024 edit 2

    =)


    • 0
      Blanc    7:30 p.m. 14 oct, 2022

      Bài này em xài mảng tiền tố dc ko ạ


      • 0
        kienhc    9:19 a.m. 3 aug, 2021

        Ra đề hơi vui hì, algorit ra đề mà kêu algorit không bik làm nhờ các bạn giúp =)))?


        • 0
          Lê_Gia_Khánh    1:23 p.m. 11 jun, 2021

          sao e bi rte vay :((


          • 1
            Vu_CG_Coder    6:08 p.m. 9 jun, 2021

            bài ni dùng deque hay hơn


            • 0
              20NguyenLeMinh    7:07 p.m. 2 jun, 2021 edited

              a