One day Jeff got hold of an integer sequence a₁, a₂, ..., 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:

• x occurs in sequence a.
• 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.

Help Jeff, find all x that meet the problem conditions.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵). The next line contains integers a₁, a₂, ..., a_n(1 ≤ a_i ≤ 10⁵). The numbers are separated by spaces.

Output

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.

Examples

Input

Copy

1 2

Output

Copy

1 2 0

Input

Copy

8 1 2 1 3 1 2 1 5

Output

Copy

4 1 2 2 4 3 0 5 0

Note

In the first test 2 occurs exactly once in the sequence, ergo p₂ = 0.

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include