1185D.md (1942B)
1 Source: https://codeforces.com/problemset/problem/1185/D 2 3 D. Extra Element 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 A sequence $a_1, a_2, \dots, a_k$ is called an arithmetic progression if for each $i$ from $1$ to $k$ elements satisfy the condition $a_i = a_1 + c \cdot (i - 1)$ for some fixed $c$. 22 23 For example, these five sequences are arithmetic progressions: $[5, 7, 9, 11]$, $[101]$, $[101, 100, 99]$, $[13, 97]$ and $[5, 5, 5, 5, 5]$. And these four sequences aren't arithmetic progressions: $[3, 1, 2]$, $[1, 2, 4, 8]$, $[1, -1, 1, -1]$ and $[1, 2, 3, 3, 3]$. 24 25 You are given a sequence of integers $b_1, b_2, \dots, b_n$. Find any index $j$ ($1 \le j \le n$), such that if you delete $b_j$ from the sequence, you can reorder the remaining $n-1$ elements, so that you will get an arithmetic progression. If there is no such index, output the number -1. 26 27 Input 28 29 The first line of the input contains one integer $n$ ($2 \le n \le 2\cdot10^5$) — length of the sequence $b$. The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — elements of the sequence $b$. 30 31 Output 32 33 Print such index $j$ ($1 \le j \le n$), so that if you delete the $j$-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 2 6 8 7 4 42 ``` 43 44 Output 45 46 ``` 47 4 48 ``` 49 50 Input 51 52 ``` 53 8 54 1 2 3 4 5 6 7 8 55 ``` 56 57 Output 58 59 ``` 60 1 61 ``` 62 63 Input 64 65 ``` 66 4 67 1 2 4 8 68 ``` 69 70 Output 71 72 ``` 73 -1 74 ``` 75 76 Note 77 78 Note to the first example. If you delete the $4$-th element, you can get the arithmetic progression $[2, 4, 6, 8]$. 79 80 Note to the second example. The original sequence is already arithmetic progression, so you can delete $1$-st or last element and you will get an arithmetical progression again.