454B.md (1144B)
1 Source: https://codeforces.com/problemset/problem/454/B 2 3 B. Little Pony and Sort by Shift 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 One day, Twilight Sparkle is interested in how to sort a sequence of integers *a*1, *a*2, ..., *a**n* in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning: 22 23 *a*1, *a*2, ..., *a**n* → *a**n*, *a*1, *a*2, ..., *a**n* - 1. 24 25 Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence? 26 27 Input 28 29 The first line contains an integer *n* (2 ≤ *n* ≤ 105). The second line contains *n* integer numbers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 105). 30 31 Output 32 33 If it's impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it. 34 35 Examples 36 37 Input 38 39 ``` 40 2 41 2 1 42 ``` 43 44 Output 45 46 ``` 47 1 48 ``` 49 50 Input 51 52 ``` 53 3 54 1 3 2 55 ``` 56 57 Output 58 59 ``` 60 -1 61 ``` 62 63 Input 64 65 ``` 66 2 67 1 2 68 ``` 69 70 Output 71 72 ``` 73 0 74 ```