Yyds dry goods inventory ＃ solve the real problem of famous enterprises: cross line

1. sketch ：

describe

Big M Assign to small M A topic ： First of all give n A point on the abscissa , Then connect them continuously with semicircles ： First connect the first point with the second point ( Take the first point and the second point as the diameter of the semicircle ). Then connect the second and third points , Until the first n A little bit . Now we need to decide whether these semicircles intersect , Intersection at the end is not a semicircle intersection . As shown in the figure below .

Input description ：

The first line of input contains an integer T (1 ≤ T ≤ 10) Express T Group example . The first line of each set of samples is an integer n (1≤n≤1000). The next line of input is n Different integers separated by spaces a1,a2,...,an (-1000000 ≤ ai ≤ 1000000),(ai,0) It means the first one i The position of a point on the abscissa .

Output description ：

For each input file , Output T That's ok . Output per row "y" Indicates that these semicircles intersect or "n".

Example 1

Input ：

Log in and copy

      
      

       
       2
       
       
4
       
       
0 10 5 15
       
       
4
       
       
0 15 5 10
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
      
      

Output ：

Log in and copy

      
      

       
       y
       
       
n
      
      
      
      

       
       
1.
       
       
2.
      
      

2. Code implementation ：

Log in and copy

      
      

      
      

       
       
1.
      
      

Log in and copy

      
      

       
       import java.util.*;
       
       
public class Main{
       
       
    public static void main(String[] args) {
       
       
        Scanner in = new Scanner(System.in);
       
       
        int T = in.nextInt();
       
       
        while (T-- > 0){
       
       
            int n = in.nextInt();// End points 
       
       
            int[] arr = new int[n];
       
       
            for (int i = 0; i < n; i++) {// Input endpoint 
       
       
                arr[i] = in.nextInt();
       
       
            }
       
       
            List<int[]> cir = new ArrayList<>();
       
       
            for (int i = 0; i < n - 1; i++) {// Storage circle 
       
       
                int left = Math.min(arr[i],arr[i + 1]);// Left end point 
       
       
                int right = Math.max(arr[i],arr[i + 1]);// Right endpoint 
       
       
                cir.add(new int[]{left,right});
       
       
            }
       
       
            // The title means that all circles do not intersect , To return to false
       
       
            boolean flag = false;
       
       
            for (int i = 1; i < cir.size(); i++) {
       
       
                for (int j = 0; j < i; j++) {
       
       
                    // First set the endpoints of the two circles 
       
       
                    int left1 = cir.get(i)[0],right1 = cir.get(i)[1];// round 1 The endpoint of 
       
       
                    int left2 = cir.get(j)[0],right2 = cir.get(j)[1];// round 2 The endpoint of 
       
       
                    // The intersection of two circles 
       
       
                    if (left1 < left2 && right1 < right2 && right1 > left2){
       
       
                        flag = true;
       
       
                        break;
       
       
                    }else if (left1 > left2 && left1 < right2 && right1 > right2){
       
       
                        flag = true;
       
       
                        break;
       
       
                    }
       
       
                }
       
       
            }
       
       
            if (flag){
       
       
                System.out.println("y");
       
       
            }else {
       
       
                System.out.println("n");
       
       
            }
       
       
        }
       
       
    }
       
       
}
       
       

      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.
       
       
28.
       
       
29.
       
       
30.
       
       
31.
       
       
32.
       
       
33.
       
       
34.
       
       
35.
       
       
36.
       
       
37.
       
       
38.
       
       
39.
       
       
40.
       
       
41.
       
       
42.