Để bảo vệ các lãnh đạo cao cấp tham gia trong lễ diễu binh và diễu hành kỷ niệm 80 năm Quốc khánh nước Cộng hòa xã hội chủ nghĩa Việt Nam, bộ phận an ninh triển khai dãy các cảm biến dọc hành lang các lãnh đạo cấp cao đang ngồi trong lúc buỗi lễ diễn ra. Mỗi cảm biến có ngưỡng cảnh báo tức là giới hạn cảnh báo trước khi phát tín hiệu không an toàn.

Để đánh giá độ an toàn của một hành lang từ cảm biến ~i~ đến cảm biến ~j~ (~1 \leq i \leq j \leq n~) trung tâm sử dụng công thức:

$$Risk(i, j) = a_i + a_j + \min(a_i, a_{i+1}, \dots, a_j)$$

Trong đó:

• ~a_i~: ngưỡng của cảm biến đầu đoạn.
• ~a_j~: ngưỡng của cảm biến cuối đoạn.
• ~min(a_i,a_{i+1},...,a_j)~: ngưỡng nhỏ nhất trong đoạn, điểm có giới hạn cảnh báo thấp nhất trong đoạn.

Một đoạn hành lang từ vị trí ~i~ đến vị trí ~j~ được coi là an toàn nếu ~Risk(i, j) \leq k~. Ngược lại, nếu vượt quá ~k~ thì đoạn hàng lang đó sẽ không an toàn.

Yêu cầu: Cho ~n~ cảm biến được đặt dọc hành lang theo thứ tự từ ~1~ đến ~n~, tại một thời điểm cảm biến thứ ~i~ có ngưỡng cảnh báo ~a_i~. Hãy đếm số lượng đoạn ~[i, j]~ là đoạn hành lang an toàn.

Input

Vào từ file văn bản SECINT.INP:

• Dòng đầu tiên: chứa hai số nguyên dương ~n, k~
  • ~n~: số lượng cảm biến (~1 \leq n \leq 100000~);
  • ~k~: ngưỡn an toàn tối đa cho phép (~0 \leq k \leq 10^9~).
• Dòng 2: chứa ~n~ số nguyên ~a_1,a_2,...,a_n~;
  • ~a_i~: ngưỡng cảnh báo của cảm biến thứ i (~0 \leq a_i \leq 10^9~)

Lưu ý: Các số trên một dòng cách nhau dấu cách.

Output

Ghi ra file văn bản SECINT.OUT số nguyên dương duy nhất là kết quả bài toán.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \leq 5000~.
• Subtask ~2~ ~(20\%)~: ~n \leq 10^5, a_i \leq a_{i+1}, 1 \leq i \leq n~.
• Subtask ~3~ ~(20\%)~: Tồn tại vị trí ~t~ sao cho ~a_1 \leq a_2 \leq ... \leq a_t \geq a_{t+1} \geq ... \geq a_n, n \leq 10^5~.
• Subtask ~4~ ~(40\%)~: Không có giới hạn gì thêm.

Example input 1

6 5 
3 4 2 6 1 3

Example output 1

4

Note 1

• Có 4 đoạn an toàn ~[1, 5]~, ~[3, 5]~, ~[5, 5]~, ~[5,6]~.

Example input 2

6 6 
4 3 1 2 5 3

Example output 2

7

Note 2

• Có 7 đoạn an toàn ~[1, 3]~, ~[2, 3]~, ~[2, 4]~, ~[3,3]~, ~[3,4]~, ~[3,6]~, ~[4,4]~.