codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2187A.md (1805B)


      1 Source: https://codeforces.com/problemset/problem/2187/A
      2 
      3 A. Restricted Sorting
      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 an array $a$ of length $n$. For an integer $k$, we call it piggy if and only if it is possible to sort $a$ in non-descending order by performing the following operation an arbitrary number of times (possibly zero):
     22 
     23 * First, select two indices $i$ and $j$ ($1 \le i \lt j \le n$) such that $|a_i - a_j| \ge k$;
     24 * Then, swap $a_i$ and $a_j$.
     25 
     26 You need to determine the largest piggy integer $k$. If such an integer does not exist, output $-1$.
     27 
     28 Input
     29 
     30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     31 
     32 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$.
     33 
     34 The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of $a$.
     35 
     36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.
     37 
     38 Output
     39 
     40 For each test case, output a single integer — the largest piggy integer $k$.
     41 
     42 If such an integer does not exist, output $-1$ instead.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 5
     50 
     51 1
     52 
     53 1
     54 
     55 5
     56 
     57 1 2 3 4 5
     58 
     59 3
     60 
     61 1 4 2
     62 
     63 5
     64 
     65 2 1 5 4 3
     66 
     67 6
     68 
     69 1 1 4 5 1 4
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 -1
     76 
     77 -1
     78 
     79 2
     80 
     81 2
     82 
     83 3
     84 ```
     85 
     86 Note
     87 
     88 In the first and the second test case, no matter how large $k$ is, you can always sort $a$ in non-descending order by not performing any operations.
     89 
     90 In the third test case, the largest piggy $k$ is $2$. We can select $i=2$ and $j=3$ in the first operation, since $|a_2-a_3|=|4-2|=2 \ge k$, and $a$ is sorted in non-descending order. It can be proven that no piggy integers larger than $2$ exist.