1671B.md (2100B)
1 Source: https://codeforces.com/problemset/problem/1671/B 2 3 B. Consecutive Points Segment 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given $n$ points with integer coordinates on a coordinate axis $OX$. The coordinate of the $i$-th point is $x_i$. All points' coordinates are distinct and given in strictly increasing order. 22 23 For each point $i$, you can do the following operation no more than once: take this point and move it by $1$ to the left or to the right (i..e., you can change its coordinate $x_i$ to $x_i - 1$ or to $x_i + 1$). In other words, for each point, you choose (separately) its new coordinate. For the $i$-th point, it can be either $x_i - 1$, $x_i$ or $x_i + 1$. 24 25 Your task is to determine if you can move some points as described above in such a way that the new set of points forms a consecutive segment of integers, i. e. for some integer $l$ the coordinates of points should be equal to $l, l + 1, \ldots, l + n - 1$. 26 27 Note that the resulting points should have distinct coordinates. 28 29 You have to answer $t$ independent test cases. 30 31 Input 32 33 The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow. 34 35 The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of points in the set $x$. 36 37 The second line of the test case contains $n$ integers $x_1 \lt x_2 \lt \ldots \lt x_n$ ($1 \le x_i \le 10^6$), where $x_i$ is the coordinate of the $i$-th point. 38 39 It is guaranteed that the points are given in strictly increasing order (this also means that all coordinates are distinct). It is also guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$). 40 41 Output 42 43 For each test case, print the answer — if the set of points from the test case can be moved to form a consecutive segment of integers, print YES, otherwise print NO. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 2 53 54 1 4 55 56 3 57 58 1 2 3 59 60 4 61 62 1 2 3 7 63 64 1 65 66 1000000 67 68 3 69 70 2 5 6 71 ``` 72 73 Output 74 75 ``` 76 YES 77 YES 78 NO 79 YES 80 YES 81 ```