[Solution] Train and Queries Codeforces Solution

C. Train and Queries

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Along the railroad there are stations indexed from 1$1$ to 109${10}^9$. An express train always travels along a route consisting of n$n$ stations with indices u1,u2,…,un$u_1,u_2,\dots ,u_n$, where (1≤ui≤109$1\le u_i\le {10}^9$). The train travels along the route from left to right. It starts at station u1$u_1$, then stops at station u2$u_2$, then at u3$u_3$, and so on. Station un$u_n$ — the terminus.

It is possible that the train will visit the same station more than once. That is, there may be duplicates among the values u1,u2,…,un$u_1,u_2,\dots ,u_n$.

You are given k$k$ queries, each containing two different integers aj$a_j$ and bj$b_j$ (1≤aj,bj≤109$1\le a_j,b_j\le {10}^9$). For each query,

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 determine whether it is possible to travel by train from the station with index aj$a_j$ to the station with index bj$b_j$.

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

Input

The first line of the input contains an integer t$t$ (1≤t≤104$1\le t\le {10}^4$) —the number of test cases in the test.

Round Down the Price Codeforces Solution

Polycarp Writes a String from Memory Codeforces Solution

Train and Queries Codeforces Solution

Not a Cheap String Codeforces Solution

Split Into Two Sets Codeforces Solution

Equate Multisets Codeforces Solution

Passable Paths (easy version) Codeforces Solution

Passable Paths (hard version) Codeforces Solution

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$n$ and k$k$ (1≤n≤2⋅105,1≤k≤2⋅105$1\le n\le 2\cdot {10}^5,1\le k\le 2\cdot {10}^5$) —the number of stations the train route consists of and the number of queries.

The third line of each test case contains exactly n$n$ integers u1,u2,…,un$u_1,u_2,\dots ,u_n$ (1≤ui≤109$1\le u_i\le {10}^9$). The values u1,u2,…,un$u_1,u_2,\dots ,u_n$ are not necessarily different.

The following k$k$ lines contain two different integers aj$a_j$ and bj$b_j$ (1≤aj,bj≤109$1\le a_j,b_j\le {10}^9$) describing the query with index j$j$.

It is guaranteed that the sum of n$n$ values over all test cases in the test does not exceed 2⋅105$2\cdot {10}^5$. Similarly, it is guaranteed that the sum of k$k$ values over all test cases in the test also does not exceed 2⋅105$2\cdot {10}^5$

Output

For each test case, output on a separate line:

• YES, if you can travel by train from the station with index aj$a_j$ to the station with index bj$b_j$
• 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).