Medium Data Structures > Range Minimum Query/Lowest Common Ancestor

Shafi and Rafi are twin brothers. They are very interested on mathematics. Shafi wants to play a game “Panouti” with his brother, Rafi, using an Array, **A**, of **n** different integers. The rules are as follows: <br/> 1. Shafi plays first and two players move in alternating turns. <br/> 2. In a single move, a player chooses the maximum element currently present in the Array, **A**, and removes it as well as all the other elements of its right. <br/>For example A = [2, 3, 5, 4, 1] then, it becomes A = [2, 3] after the first move, because we remove the maximum element (i.e., 5) and all elements to its right (i.e., 4 and 1).If there are more than one maximum element then leftmost will be choosen.<br/> 3. The modifications made to the array during each turn are permanent, so the next player (Rafi) continues the game with the remaining array. <br/> 4. For each turn every players get a Point. This Point actually the position of the maximum element which Shafi or Rafi turned. <br/> 5. If the difference between total Shafi’s point and Rafi’s point is a Prime number then Rafi will win otherwise Shafi will win. <br/> Now, Shafi and Rafi play **g** games. Given the initial array of each games. Can you find and print the name of the winner? <br/> <br/> If Shafi wins print: Shafi=X (one space) Rafi=Y Shafi win Else print: Rafi=Y (one space) Shafi=X Rafi win Where X and Y is the total points of Shafi and Rafi. Input: ---------- The first line contains a single integer denoting **g** (the number of games). The **2*g** subsequent lines describe each game array over two lines: <br/> 1. The first line contains a single integer, **n** , denoting the number of elements in array **A**. <br/> 2. The second line contains **n** different space-separated integers describing the respective values of **a<sub>1** </sub>, **a <sub>2** </sub>, **a<sub>3**</sub> …. **a<sub>n**</sub> for array **A**. <br/> Constraints: ---------- 0 < g < 51 <br/> 0 < n < 10001 <br/> 0 < a <sub>i</sub> < 1000001 <br/> **summation of n over all games will be 10000.** Output: ---------- For each game, print the total points and name of the winner on a new line. You may follow the above instructions and Sample input output format. Sample Input 1 5 5 2 6 3 4 Sample Output Game 1: Rafi=1 Shafi=3 Rafi win *Analysis: You have an array of elements [5, 2, 6, 3, 4] <br/> Shafi will turn 6, so Shafi’s point = 3 (position of the largest number), then all right numbers will be reduced. So, you have [5, 2] <br/> Rafi will turn 5 and his point = 1(position of the largest number), then all right numbers will be reduced. So, you have [] empty array. <br/> Now the difference between Shafi’s point and Rafi’s point is 2 (3-1=2) is a Prime number, as a result Rafi will win.* > N:B: see the detail of prime numbers > https://en.wikipedia.org/wiki/Prime_number

Pranta Sarker