Week 3 Practice Programming Assignment 1

Help the passengers A taxi service has been running in the city. There are a total of 109 stops numbered from 1 to 109 at which pick up and drop is allowed from the taxi. You are given a schedule of a taxi being run by the taxi service. The schedule is in form a list of stops, S = [s1, s2, …, sN]. The taxi starts from the stop s1, then it goes to each of the stops s2, s3, …, sN one by one (i.e. it goes to each of the stops in the list from left to right) and its journey terminates at the Nth stop sN. Note that S can contain the same stop multiple times, i.e. the taxi can go to one stop multiple times. You are given Q queries of the form (si, sj), i.e. one passenger wants to go from the stop si to sj using this taxi and the passenger will use the taxi only if he/she can go from stop si to sj only using this taxi, i.e. the taxi must pick him/her up from stop si and drop him/her at stop sj. Your task is to find out exactly how many of these Q passengers can use this taxi. For example, S = [2, 4, 1, 2, 6, 3, 4, 5], Q = 2, the two queries are as follows: i) (2, 3): This passenger can take the taxi at stop 2 and can reach reach to stop 3 via the path 2 → 6 → 3. ii) (3, 1): This passenger can not use the taxi as it does not go to stop 1 after reaching stop 3. So, only 1 passenger can use the taxi. Input Format: The first line is T (1 ≤ T ≤ 104), the number of testcases. Then each testcase is given as follows: First line of each testcase contains two space separated integers: N (1 ≤ N ≤ 105) and Q (1 ≤ Q ≤ 105). The next line of each testcase contains N space separated integers: s1, s2, ..., sN. (1 ≤ si ≤ 109) Next Q lines of each testcase contains a query on each line, a query is given as two space separated integers: si sj (si ≠ sj). Output Format: For each testcase output the exact number of passengers out of Q who can use the taxi in a single line. So, the output should contain T lines.