Almost Sorted Permutation
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a sequence of n distinct numbers a[1..n], we want to sort them in an ascending order.
An interesting property of some sequences is that all numbers are almost at their correct position! More formally, the distance between the current position of any value is at most 1 from its correct position in a sorted order.
Now, you want to verify whether the input sequence has such a property.
Note that the time limit for this problem is 0.2 seconds. Please try to write a very efficient algorithm and implementation.
The first line contains an integer T denoting the total number of test cases.
For each test case, the first line contains a single integer n, and the second line contains a[1..n] as a single space-separated list.
For each test case, output "YES" or "NO" (without quotes) to indicate whether the input sequence has such a property.
- 1 <= T <= 10
- 1 <= n <= 10^6
- 1 <= a[i] <= 10^9
Input: 2 3 1 2 3 5 2 4 1 3 5 Output: YES NO
|Tags||ad-hoc, cook63, shangjingbo, simple|
|Time Limit:||0.2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.