# Right search algorithm idea

The following is a programming problem of byte jumping on the network. I wrote a solution with a time complexity of O(n*n), but it timed out. Later, I saw an algorithm with a time complexity of O(n). I called it to explore the algorithm to the right.

Time limit: 1 second for C / C + + and 2 seconds for other languages

Space limit: C/C++ 128M, other languages 256M

My name is Wang Dashi. I'm an agent. I have just received a task: ambush in the street of byte jump to catch the terrorist Kong lianshun. I'm working with two other agents, and I suggest

1. We chose three ambush sites out of N buildings in bytechop street.
2. In order to take care of each other, we decided that the distance between the two agents farthest away should not exceed D.

I'm a genius! After careful calculation, we chose one of the X feasible ambush schemes. This plan is foolproof, tremble, Kong lianshun!
......
Unexpectedly, the plan failed. Kong lianshun disguised as a little dragon girl and escaped from the street of byte jump in cosplay's team. It's just that his disguise is too successful. Even when Yang Guo comes, he can't find it!

Listen to the question: given N (the number of buildings that can be used as the ambush point), D (the maximum distance between the two agents farthest away) and the coordinates of the optional buildings, calculate how many ambush options the sledgehammer team has in this operation.
Be careful:

1. Two agents can't ambush in the same place
2. The three agents are equivalent: that is, the same location combination (A, B, C) is only an ambush method and cannot be reused because of "agents exchange positions"

Enter a description:
The first line contains two numbers, N and D, separated by spaces (1   n   n  ; 1000000; 1   D   1000000)

The second line contains the positions of N buildings, each of which is represented by an integer (value range is [0, 1000000]), arranged from small to large (byte jumping street is regarded as a number axis)

Output Description:
A number indicating the number of different ambush schemes. The result may overflow. Please take the mold for 99997867

Input example 1:
4 3
1 2 3 4

Output example 1:
4

Example 1:
Options (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)

Input example 2:
5 19
1 10 20 30 50

Output example 2:
1

Example 2:
Options (1, 10, 20)

Own code:

```import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
List<Integer> list = new ArrayList<Integer>();
for(int i = 0;i<n;i++) {
}

Main e2 = new Main();
int ans = e2.solution(n,m,list);
System.out.println(ans);
}
public int solution(int n,int m,List<Integer> list) {
int ans = 0;
int temp = 2;
if(n<2) return 0;
for(int i = 0;i<n-2;i++) {
for(int j = temp;j<n;j++) {
if((list.get(j)-list.get(i))<=m) {
ans = ans + (j-i-1);
}
}
temp++;
}
return ans%99997867;
}
}
```

Code idea: two iterations, the left side (head) of the traversal value of the outer side and the right side (tail) of the traversal value of the inner layer.

Correct code:

```import java.util.Scanner;

private int mod = 99997867;

private void sln() {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), D = sc.nextInt();
long cnt = 0;
if (N <= 2) {
System.out.println(-1);
return;
}
int[] locs = new int[N];
for (int i = 0; i < N; i++) {
locs[i] = sc.nextInt();
}
sc.close();
int left = 0, right = 2;
while (right < N) {
if (locs[right] - locs[left] > D) left++;
else if (right - left < 2) right++;
else {
cnt += calC(right - left);
right++;
}
}
cnt %= mod;
System.out.println(cnt);
}

private long calC(long num) {
return num * (num - 1) / 2;
}

public static void main(String[] args) {  