codeforces-scrape

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

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.