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:

  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^5). The next line contains integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). 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
1
2

Output
1
2 0

Input
8
1 2 1 3 1 2 1 5

Output
4
1 2
2 4
3 0
5 0



-----Note-----

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

Difficulty: interview

Starter code:

Solutions:
import sys

def Is_arth(L):
    D=L[1]-L[0]
    p=L[1]
    for i in range(2,len(L)):
        if(L[i]-p!=D):
            return False
        p=L[i]
    return True

n=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))

T=[False]*(10**5+1)
Z=[]
for i in range(10**5+1):
    Z.append([])

Taken=[]
for i in range(n):
    Z[A[i]]+=[i]


Ans=""
Num=0
for i in range(10**5+1):
    L=len(Z[i])
    item=i
    if(L==0):
        continue
    if(L==1):
        Num+=1
        Ans+=str(item)+" 0\n"
    elif(L==2):
        Num+=1
        Ans+=str(item)+" "+str(Z[item][1]-Z[item][0])+"\n"
    else:
        if(Is_arth(Z[item])):
            Num+=1
            Ans+=str(item)+" "+str(Z[item][1]-Z[item][0])+"\n"
sys.stdout.write(str(Num)+"\n")
sys.stdout.write(Ans)


n = int(input())
a = list(map(int, input().split()))

N = 100001
d = [-1] * N
p = [-1] * N
for i in range(n):
  if p[a[i]] == -1:
    d[a[i]] = 0
  else:
    if i - p[a[i]] != d[a[i]]:
      if d[a[i]] == 0:
        d[a[i]] = i - p[a[i]]
      else:
        d[a[i]] = -1
  p[a[i]] = i

count = 0
for i in range(N):
  if d[i] != -1:
    count += 1
print(count)
print('\n'.join("{0} {1}".format(i, d[i]) for i in range(N) if d[i] != -1))

def AP(seq):
    d = seq[1]-seq[0]
    for i in range(1, len(seq)-1):
        if seq[i+1]-seq[i]!=d:
            return -1
    return d

def main():
    n = int(input())
    s = input().split()
    data = {}
    answer = []

    for i in range(0, len(s)):
        item = s[i]
        if item in data:
            data[item]+=[i]
        else:
            data[item]=[i]

    uniq = [int(item) for item in list(data.keys())]
    uniq.sort()

    for x in uniq:
        iters = data[str(x)]
        count = len(iters)

        if count==1:
            answer.append([x, 0])
            continue
        #else:
        d = AP(iters)
        if d!=-1:
            answer.append([x, d])

    t = len(answer)
    print(t)
    s=''
    for a,b in answer:
        s+=str(a)+' '+str(b)+'\n'
    print(s[:-1])

main()


3

def readln(): return tuple(map(int, input().split()))

n, = readln()
var = {}
for i, a in enumerate(readln()):
    if a in var:
        var[a].append(i)
    else:
        var[a] = [i]
ans = []
for x, v in list(var.items()):
    if len(v) == 1:
        ans.append((x, 0))
    else:
        d = set([v[i] - v[i - 1] for i in range(1, len(v))])
        if len(d) == 1:
            ans.append((x, d.pop()))
print(len(ans))
print('\n'.join('%d %d' % f for f in sorted(ans)))


n = int(input())
A = [int(i) for i in input().split()]

table = [None for i in range(100001)]

for i,x in enumerate(A):
	if table[x] == None:
		table[x] = [i,0]
	else:
		previ = table[x][0]
		if previ == -1:
			continue
		prevp = table[x][1]
		if prevp == 0:
			table[x][0] = i
			table[x][1] = i - previ
		else:
			currentp = i - previ
			if currentp == prevp:
				table[x][0] = i
			else:
				table[x][0] = -1

output = [(x,t[1]) for x,t in enumerate(table) if t != None and t[0] != -1]
s = str(len(output)) + '\n'
for x,p in output:
	s += str(x) + ' ' + str(p) + '\n'
print(s)

#! /usr/bin/python3

n = int(input())
#a = list(map(int, input().split()))
a = tuple(map(int, input().split()))
u = {}
v = {}
w = []

for i, x in enumerate(a):
    if x in v:
        v[x].append(i)
    else:
        v[x] = [i]

for x, li in list(v.items()):
    if len(li) == 1:
        w.append((x, 0))
    else:
        s = set([li[i] - li[i - 1] for i in range(1, len(li))])
        if len(s) == 1:
            w.append((x, s.pop()))

print(len(w))

print('\n'.join('%d %d' %x for x in sorted(w)))


#! /usr/bin/python3

n = int(input())
a = list(map(int, input().split()))
#a = tuple(map(int, input().split()))
u = {}
v = {}
w = []

for i, x in enumerate(a):
    if x in v:
        v[x].append(i)
    else:
        v[x] = [i]

for x, li in list(v.items()):
    if len(li) == 1:
        w.append((x, 0))
    else:
        s = set([li[i] - li[i - 1] for i in range(1, len(li))])
        if len(s) == 1:
            w.append((x, s.pop()))

print(len(w))

print('\n'.join('%d %d' %x for x in sorted(w)))


#! /usr/bin/python3

n = int(input())
a = list(map(int, input().split()))
#a = tuple(map(int, input().split()))
u = {}
v = {}
w = []

for i, x in enumerate(a):
    if x in v:
        v[x].append(i)
    else:
        v[x] = [i]

for x, li in list(v.items()):
    if len(li) == 1:
        w.append((x, 0))
    else:
        d = li[1] - li[0]
        sign = True
        for i in range(1, len(li)):
            if li[i] - li[i - 1] != d:
                sign = False
        if sign:
            w.append((x, d))

print(len(w))

print('\n'.join('%d %d' %x for x in sorted(w)))


from collections import defaultdict
n = input()
t = list(map(int, input().split()))
p, d = defaultdict(int), defaultdict(int)

for i, x in enumerate(t, 1):
    if d[x] < 0: continue
    if p[x]: 
        if d[x] and i != p[x] + d[x]: d[x] = -1
        else: d[x] = i - p[x]
    p[x] = i

y = list(d.keys())
y.sort()

t = list(str(x) + ' ' + str(d[x]) for x in y if d[x] >= 0)
print(len(t))
print('\n'.join(t)) 

from collections import defaultdict
n = input()
t = list(map(int, input().split()))
p, d = defaultdict(int), defaultdict(int)

for i, x in enumerate(t, 1):
    if d[x] < 0: continue
    if p[x]: 
        if d[x] and i != p[x] + d[x]: d[x] = -1
        else: d[x] = i - p[x]
    p[x] = i

y = list(d.keys())
y.sort()

t = list('{0} {1}'.format(x, d[x]) for x in y if d[x] >= 0)
print(len(t))
print('\n'.join(t)) 

import sys

def Is_arth(L):
    D=L[1]-L[0]
    p=L[1]
    for i in range(2,len(L)):
        if(L[i]-p!=D):
            return False
        p=L[i]
    return True

n=int(sys.stdin.readline())

A=list(map(int,sys.stdin.readline().split()))

T=[False]*(10**5+1)
Z=[]
for i in range(10**5+1):
    Z.append([])

Taken=[]
for i in range(n):
    Z[A[i]]+=[i]


Ans=""
Num=0
for i in range(10**5+1):
    L=len(Z[i])
    item=i
    if(L==0):
        continue
    if(L==1):
        Num+=1
        Ans+=str(item)+" 0\n"
    elif(L==2):
        Num+=1
        Ans+=str(item)+" "+str(Z[item][1]-Z[item][0])+"\n"
    else:
        if(Is_arth(Z[item])):
            Num+=1
            Ans+=str(item)+" "+str(Z[item][1]-Z[item][0])+"\n"
sys.stdout.write(str(Num)+"\n")
sys.stdout.write(Ans)


n = int(input())
inp, k = {},0

# for i in input().split(" "):
#     if int(i) not in list(inp.keys()):   inp[int(i)] = [k]
#     else: inp[int(i)]+=[k]
#     k+=1

s = input().split()

for i in range(0, len(s)):
    item = int(s[i])
    if item in inp:
        inp[item]+=[i]
    else:
        inp[item]=[i]

inp_keys = [int(i) for i in inp.keys()]
inp_keys.sort()
result = []

def check(arr):
    diff = arr[1]-arr[0]
    for i in range(1, len(arr)-1):
        if arr[i+1]-arr[i] != diff: return False
    return diff

for i in inp_keys:
    j = inp[i]
    if len(j) == 1:
        result.append([i,0])
        continue
    diff = check(j)
    if diff:   result.append([i,diff])

out = ""
for i,j in result: out+=str(i)+" "+str(j)+"\n"

print(len(result))
print(out[:-1])

inp, k = {},0
n,s = int(input()),input().split()

for i in range(0, len(s)):
    inp_k = int(s[i])
    if inp_k  in inp: inp[inp_k ]+=[i]
    else: inp[inp_k] =[i]

inp_keys = [int(i) for i in inp.keys()]
inp_keys.sort()
result = []

def check(arr):
    diff = arr[1]-arr[0]
    for i in range(1, len(arr)-1):
        if arr[i+1]-arr[i] != diff: return False
    return diff

for i in inp_keys:
    j = inp[i]
    if len(j) == 1:
        result.append([i,0])
    else:
        diff = check(j)
        if diff: result.append([i,diff])

out = ""
for i,j in result: out+=str(i)+" "+str(j)+"\n"
print(str(len(result))+"\n" + out[:-1])

n = int(input())
a = [(int(x), y) for x, y in zip(input().split(), list(range(n)))]
a.sort()
i = j = 0
l = []
while i < n:
	while j < n and a[i][0] == a[j][0]:
		j += 1
	i += 1
	if i == j:
		l.append(str(a[i - 1][0]) + ' 0')
	else:
		k = a[i][1] - a[i - 1][1]
		while i < j and a[i][1] - a[i - 1][1] == k:
			i += 1
		if i == j:
			l.append(str(a[i - 1][0]) + ' ' + str(k))
	i = j
print(len(l))
print('\n'.join(l))


def main():
    input()
    aa = [0] * 200002
    for i, x in enumerate(map(int, input().split()), 1):
        x *= 2
        j, step = aa[x], aa[x + 1]
        if j:
            if step:
                if j + step != i:
                    aa[x + 1] = -1
            else:
                aa[x + 1] = i - j
        aa[x] = i
    res = []
    for x in range(2, len(aa), 2):
        j, step = aa[x], aa[x + 1]
        if j and step != -1:
            res.append(' '.join((str(x // 2), str(step))))
    print(len(res))
    print('\n'.join(res))


def __starting_point():
    main()
__starting_point()

a = int(input())
seq = list(map(int, input().split()))
mass = {}
for i in range(a):
    if seq[i] in mass:
        mass[seq[i]].append(i)
    else:
        mass[seq[i]] = [i]
tmp_mass = []
for key, value in list(mass.items()):
    flag = True
    if len(value) == 1:
        tmp_mass.append((key, 0))
        continue
    elif len(value) == 2:
        tmp_mass.append((key, value[1] - value[0]))
        continue
    else:
        for i in range(len(value) - 2):
            if value[i+2] - value[i+1] == value[i+1] - value[i]:
                pass
            else:
                flag = False
        if flag:
            tmp_mass.append((key, value[len(value)-1] - value[len(value)-2]))
print(len(tmp_mass))
tmp_mass.sort(key = lambda x: x[0])
for i in range(len(tmp_mass)):
    print(' '.join(map(str, tmp_mass[i])))


n = int(input())
a = [int(i) for i in input().split()]
occ = dict()
for i in range(0, len(a)):
    if a[i] not in list(occ.keys()):
        occ[a[i]] = []
    occ[a[i]].append(i)
t = 0
out = ""
for k in sorted(occ.keys()):
    ini = occ[k][0]
    diff = 0
    if len(occ[k]) > 1:
        diff = occ[k][1] - occ[k][0]
    valid = True
    for i in range(2, len(occ[k])):
        if occ[k][i] - occ[k][i - 1] != diff:
            if a[0] == 100000:
                print(str(occ[k][i - 1]) + " " + str(occ[k][i]))
                return
            valid = False
            break
    if valid:
        out += (str(k) + " " + str(diff) + "\n")
        t += 1    
print(str(t) + "\n" + out)


_ = input()
numbers = {}

for index, num in enumerate(input().split()):
    num = int(num)
    try: numbers[num].append(index)
    except: numbers[num] = [index]

temp = {}
size = 0

for num, ind in numbers.items():
    try: prog = ind[1] - ind[0]
    except IndexError: 
        temp[num] = 0
        size += 1
        continue

    for i in range(2, len(ind)):
        new_prog = ind[i] - ind[i - 1]
        if new_prog != prog:
            prog = -1
            break

    if prog != -1:
        temp[num] = prog
        size += 1

print(size)

keys = sorted(temp.keys())

for key in keys:
    print(key, temp[key])

n = int(input())
b = [(int(x), y) for x, y in zip(input().split(), list(range(n)))]
b.sort()
b+=[(0,0)]
t=0
ans=[]
i=0
seq=0
while i<n:
    while b[i][0]!=b[i+1][0]:
        ans.append(str(b[i][0])+" 0")
        i+=1
        if i==n:
            break
    if i==n:
        i+=1
    elif b[i][0]==b[i+1][0]:
        seq=0
        while b[i][0]==b[i+1][0]:
            if seq==0:
                seq=b[i+1][1]-b[i][1]
                i+=1
            elif b[i+1][1]-b[i][1]==seq:
                i+=1
            else:
                seq=-1
                i+=1
        if seq==-1:
            i+=1
        else:
            ans.append(str(b[i][0])+" "+str(seq))
            i+=1

            
print(len(ans))
print("\n".join(ans))


n = int(input())
a = list(map(int, input().split()))

x = 100001

p = [-1] * x
l = [-1] * x
t = 0

for i in range(n):
    if p[a[i]] == -1:
        p[a[i]] = 0
        l[a[i]] = i
    elif p[a[i]] == 0:
        p[a[i]] = i - l[a[i]]
        l[a[i]] = i
    elif p[a[i]] > 0:
        if p[a[i]] == i - l[a[i]]:
            l[a[i]] = i
        else:
            p[a[i]] = -2
s=""
for i in range(x):
    if p[i] >= 0:
        t += 1
        s += str(i)+" "+ str(p[i])+"\n"
print(t)
print(s)

# http://codeforces.com/problemset/problem/352/B
get=lambda:(list(map(int,input().split())))
def isap(l):
    if len(l)<2:
        return len(l)-1
    d=l[1]-l[0]
    i=0
    n=len(l)
    while i<n-1:
        if l[i+1]-l[i]!=d:
            return -1
        i+=1
    return d
o=33
n=int(input())
l=get()
from collections import defaultdict
d=defaultdict(lambda :[])
for j,i in enumerate(l):
    d[i].append(j)
ans={}
#print(d)
for x in d:
    t=isap (d[x])
    if t !=-1:
        ans[x]=t
print(len(ans))
for i in sorted(ans):
    print(i,ans[i])

    


from collections import defaultdict

def main():
    n = int(input())
    a = list(map(int, input().split(' ')))
    
    m = defaultdict(list)
    for i in range(n):
        m[a[i]].append(i)

    ret = []
    for k in m:
        if len(m[k]) == 1:
            ret.append((k, 0))
        else:
            v = m[k]
            diff = None
            good = True
            for i in range(1, len(v)):
                d = v[i] - v[i-1]
                if diff == None:
                    diff = d
                else:
                    if diff != d:
                        good = False
                        break
            if i == len(v) - 1 and good:
                ret.append((k, diff))
    ret = sorted(ret, key=lambda x: x[0])
    print(len(ret))
    for r in ret:
        print(r[0], r[1])

main()


from collections import defaultdict

def main():
    n = int(input())
    a = list(map(int, input().split(' ')))
    
    m = defaultdict(list)
    for i in range(n):
        m[a[i]].append(i)

    ret = []
    for k in m:
        if len(m[k]) == 1:
            ret.append((k, 0))
        else:
            v = m[k]
            diff = None
            good = True
            for i in range(1, len(v)):
                d = v[i] - v[i-1]
                if diff == None:
                    diff = d
                elif diff != d:
                    good = False
                    break
            if i == len(v) - 1 and good:
                ret.append((k, diff))
    ret = sorted(ret, key=lambda x: x[0])
    print(len(ret))
    for r in ret:
        print(r[0], r[1])

main()


raselBhai = lambda:list(map(int,input().split()))

n = int(input())
lst = raselBhai()
m = 10**5+5
dst = [-1] * m
pst = [-1] * m
for i in range(n):
    if pst[lst[i]] == -1:
        dst[lst[i]] = 0
    else:
        if i - pst[lst[i]] != dst[lst[i]]:
            if dst[lst[i]] == 0:
                dst[lst[i]] = i - pst[lst[i]]
            else:
                dst[lst[i]] = -1
    pst[lst[i]] = i
cnt = 0
for i in range(m):
    if dst[i] != -1:
        cnt += 1
print(cnt)
'''for i in range(m):
    if dst[i] != -1:
        print('\n'.join("{0} {1}".format(dst[i])))'''
print('\n'.join("{0} {1}".format(i, dst[i]) for i in range(m) if dst[i] != -1))