**Train and Queries solution codeforces** – Along the railroad there are stations indexed from 11 to 109109. An express train always travels along a route consisting of 𝑛n stations with indices 𝑢1,𝑢2,…,𝑢𝑛u1,u2,…,un, where (1≤𝑢𝑖≤1091≤ui≤109). The train travels along the route from left to right. It starts at station 𝑢1u1, then stops at station 𝑢2u2, then at 𝑢3u3, and so on. Station 𝑢𝑛un — the terminus.

## [Solution] Train and Queries solution codeforces

It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values 𝑢1,𝑢2,…,𝑢𝑛u1,u2,…,un.

You are given 𝑘k queries, each containing two different integers 𝑎𝑗aj and 𝑏𝑗bj (1≤𝑎𝑗,𝑏𝑗≤1091≤aj,bj≤109). For each query, determine whether it is possible to travel by train from the station with index 𝑎𝑗aj to the station with index 𝑏𝑗bj.

For example, let the train route consist of 66 of stations with indices [3,7,1,5,1,43,7,1,5,1,4] and give 33 of the following queries:

- 𝑎1=3a1=3, 𝑏1=5b1=5It is possible to travel from station 33 to station 55 by taking a section of the route consisting of stations [3,7,1,53,7,1,5]. Answer: YES.
- 𝑎2=1a2=1, 𝑏2=7b2=7You cannot travel from station 11 to station 77 because the train cannot travel in the opposite direction. Answer: NO.
- 𝑎3=3a3=3, 𝑏3=10b3=10It is not possible to travel from station 33 to station 1010 because station 1010 is not part of the train’s route. Answer: NO.

## [Solution] Train and Queries solution codeforces

The first line of the input contains an integer 𝑡t (1≤𝑡≤1041≤t≤104) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case is empty.

The second line of each test case contains two integers: 𝑛n and 𝑘k (1≤𝑛≤2⋅105,1≤𝑘≤2⋅1051≤n≤2⋅105,1≤k≤2⋅105) —the number of stations the train route consists of and the number of queries.

The third line of each test case contains exactly 𝑛n integers 𝑢1,𝑢2,…,𝑢𝑛u1,u2,…,un (1≤𝑢𝑖≤1091≤ui≤109). The values 𝑢1,𝑢2,…,𝑢𝑛u1,u2,…,un are not necessarily different.

The following 𝑘k lines contain two different integers 𝑎𝑗aj and 𝑏𝑗bj (1≤𝑎𝑗,𝑏𝑗≤1091≤aj,bj≤109) describing the query with index 𝑗j.

It is guaranteed that the sum of 𝑛n values over all test cases in the test does not exceed 2⋅1052⋅105. Similarly, it is guaranteed that the sum of 𝑘k values over all test cases in the test also does not exceed 2⋅1052⋅105

## [Solution] Train and Queries solution codeforces

For each test case, output on a separate line:

- YES, if you can travel by train from the station with index 𝑎𝑗aj to the station with index 𝑏𝑗bj
- NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as a positive response).

3 6 3 3 7 1 5 1 4 3 5 1 7 3 10 3 3 1 2 1 2 1 1 2 4 5 7 5 2 1 1 1 2 4 4 1 3 1 4 2 1 4 1 1 2

## [Solution] Train and Queries solution codeforces

YES NO NO YES YES NO NO YES YES NO YES

The first test case is explained in the problem statement.