Please show all steps and answer question according to what is asked in question:Programming Question

The best way to learn a data structure or an algorithm is to code it up$.$ In this assignment, we have a programming

exercise for which you will be asked to write some code and submit it$.$ You may also be asked to include a write$-$up

about your code in the PDF file that you submit. Make sure to maintain your academic integrity carefully, and

protect your own work. All code submissions will be checked for plagiarism at the end of the term. It is much better

to take the hit on a lower mark than risking much worse consequences by committing an academic offence.

$[10]$ Consider the game of "Sorting Hockey Pucks" as depicted in the following diagrams $($Figure $1$ and $2).$ Initially, a

sequence of $N$ hockey pucks are placed at the START area. The pucks are numbered $1,2,3,$dots,$N$ but are arbitrarily

ordered. The goal of the player is to move the pucks out of the EXIT on the left side in the exact order of $1,2,3,$

$...,N.$ However, it might not be possible to move out all $N$ pucks in that exact order. We will write a program to

determine $K,$ the largest number of the pucks that can be moved out in the exact order of $1,2,$dots,$K.$

As you can see in the diagram, there is a BUFFER LINE that you may temporarily move the pucks to$.$ One important

rule about moving a puck into$/$out of the buffer line is that the puck can only turn left as indicated by the turning

arrows in the figures.

Figure $1$: Example of the initial state of a game

Figure $2$: The final state of the above game example.

Download the starter file A$1$Q$2.$ java, and complete the solve function. It takes an array, and returns $K,$ the largest

number of the pucks that can be moved out in the exact order of $1,2,$dots,$K.$ If the array is of length $N,$ then its

elements are guaranteed to be a permutation of the $N$ integers from $1$ to $N.$

Your implementation must make use of one or more Stack or Queue objects, and you will explain the usage of

them in your PDF file.

Read all instructions in the starter code carefully. In particular, make sure to NOT modify the parts of the starter code

that says $"$DO NOT MODIFY" in the comments, e$.$g$.,$ the package declaration "package A$1"$ and the import lines.

As an example, for the game shown in Figure $1,$ the input array would be $4,5,2,1,3,$ and the solve function

should return $3,$ according to the final state illustrated in Figure $2.$

The main function of the starter code includes a few test cases that you may use to test your own code. These test cases

are not meant to be exhaustive so passing them does not necessarily mean your program is correct. You're encouraged

to create more test cases to test your program more thoroughly.

You may setup the Java project using any programming IDE of your choice such as IntelliJ, Eclipse, VSCode, or Notepad

$$ it doesn't matter as long as the $A2Q2.$ java file is correct. Be careful: sometimes the IDE automatically inserts lines

of code such as the package declaration and imports. Make sure to double$-$check your code before submission to remove

any unnecessary those extra lines since they may cause all test cases to fail in auto$-$testing. Here is the starter code. Only implement solve function: package A$1$;

$//$ Do NOT modify the package declaration

import java.util.ArrayList;

$//$ Do NOT add any import

$//$ You may implement a new class here, such as a Stack or a Queue.

$//$ Any additional class that you use must be included in THIS file.

public class A$1$Q$2\{$

$/**$

$*$ The function that you need to implement.

$*$ Read the assignment handout for the specification.

$*$

$*$ DO NOT MODIFY the declaration of the function $($its parameter types and return type$).$

$*/$

public static int solve$($int$[]$ arr$)\{$

$//$ TODO: implement this function

return $0$;

$\}$

$/**$

$*$ This main function contains a few test cases that can be used to check

$*$ that your code compiles and runs. Note that these test cases are NOT complete,

$*$ and you need to test your code thoroughly with more cases.

$*/$

public static void main$($String$[]$ args$)\{$

$//$ Printing "true" means the return value is correct.

int$[]$ arr $=\{4,5,2,1,3\}$;

System.out.println$(3==$ solve$($arr$))$;

arr $=$ new int$[]\{5,4,3,1,2\}$;

System.out.println$(5==$ solve$($arr$))$;

arr $=$ new int$[]\{1\}$;

System.out.println$(1==$ solve$($arr$))$;

arr $=$ new int$[]\{2,3,1\}$;

System.out.println$(1==$ solve$($arr$))$;

arr $=$ new int$[]\{7,1,5,4,3,2,8,10,9,6\}$;