352B.md (1437B)
1 Source: https://codeforces.com/problemset/problem/352/B 2 3 B. Jeff and Periods 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 Jeff got hold of an integer sequence *a*1, *a*2, ..., *a**n* of length *n*. The boy immediately decided to analyze the sequence. For that, he needs to find all values of *x*, for which these conditions hold: 22 23 * *x* occurs in sequence *a*. 24 * Consider all positions of numbers *x* in the sequence *a* (such *i*, that *a**i* = *x*). These numbers, sorted in the increasing order, must form an arithmetic progression. 25 26 Help Jeff, find all *x* that meet the problem conditions. 27 28 Input 29 30 The first line contains integer *n* (1 ≤ *n* ≤ 105). The next line contains integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 105). The numbers are separated by spaces. 31 32 Output 33 34 In the first line print integer *t* — the number of valid *x*. On each of the next *t* lines print two integers *x* and *p**x*, where *x* is current suitable value, *p**x* is the common difference between numbers in the progression (if *x* occurs exactly once in the sequence, *p**x* must equal 0). Print the pairs in the order of increasing *x*. 35 36 Examples 37 38 Input 39 40 ``` 41 1 42 2 43 ``` 44 45 Output 46 47 ``` 48 1 49 2 0 50 ``` 51 52 Input 53 54 ``` 55 8 56 1 2 1 3 1 2 1 5 57 ``` 58 59 Output 60 61 ``` 62 4 63 1 2 64 2 4 65 3 0 66 5 0 67 ``` 68 69 Note 70 71 In the first test 2 occurs exactly once in the sequence, ergo *p*2 = 0.