Crossing Blocks solution codechef

Crossing Blocks solution codechef

Chef is very adventurous, so he asked Bob to give him a task.

Bob gave him a sequence of blocks with heights A1,A2,,ANA1,A2,…,AN. Chef is at the first block and he has to reach the NN-th block using the minimum number of moves to complete the task.

In one move, he can jump from the ii-th block to the jj-th block only if the following conditions are satisfied:

  • i<ji<j Crossing Blocks solution codechef 
  • AiAjAi≥Aj
  • for all kk (i<k<ji<k<j), AkAjAk≤Aj

You have to find the minimum number of moves Chef needs to perform to reach the last block, or determine that it is impossible.

Input Format Crossing Blocks solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

For each test case, print a single line containing one integer — the minimum number of moves or 1−1 if it is impossible to reach the last block.

Constraints

  • 1T1001≤T≤100
  • 2N1052≤N≤105
  • 0Ai1050≤Ai≤105 for each valid ii
  • the sum of NN over all test cases does not exceed 106106

Subtasks Crossing Blocks solution codechef

Subtask #1 (30 points):

  • 2N1,0002≤N≤1,000
  • the sum of NN over all test cases does not exceed 51045⋅104

Subtask #2 (70 points): original constraints

Sample Input 1 

2
5
9 15 8 13 8
9
20 16 13 9 17 11 15 8 7

Sample Output 1  Crossing Blocks solution codechef 

-1
4

Explanation

Example case 1: There is no way to move from the first block (with height 99) to any other block.

Example case 2: The only sequence of 44 moves is 2017158720→17→15→8→7. For example, in the first move, all the heights between 2020 and 1717 do not exceed 1717, so all conditions are satisfied.

Comments 

Leave a Comment