One day Jeff got hold of an integer sequence a1, a2, ..., an 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 ai = 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 ≤ 105). The next line contains integers a1, a2, ..., an (1 ≤ ai ≤ 105). 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 px, where x is current suitable value, px is the common difference between numbers in the progression (if x occurs exactly once in the sequence, px 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 p2 = 0.
import java.io.*;
import java.util.*;

public class Solution {

    void solve() throws IOException {
        int n = in.nextInt();
        List<List<Integer>> a = new ArrayList<>(100001);

        for (int i = 0; i <= 100001; i++) {
            a.add(new ArrayList<>());
        }

        int max = -1;
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            max = Math.max(x, max);
            a.get(x).add(i);
        }

        int[] num = new int[n], dif = new int[n];
        int sz = 0;
        for (int i = 1; i <= max; i++) {
            if (a.get(i).isEmpty()) continue;

            boolean equalDif = true;
            List<Integer> b = a.get(i);

            for (int j = 0; j < a.get(i).size() - 2 && equalDif; j++) {
                equalDif = b.get(j + 2) - b.get(j + 1) == b.get(j + 1) - b.get(j);
            }

            if (equalDif) {
                num[sz] = i;
                dif[sz] = (b.size() == 1 ? 0 : b.get(1) - b.get(0));
                sz++;
            }
        }

        StringBuilder ans = new StringBuilder(3 * sz);
        ans.append(sz).append('\n');
        for (int i = 0; i < sz; i++) {
            ans.append(num[i]).append(' ').append(dif[i]).append('\n');
        }
        System.out.println(ans.toString());
    }

    public void run() throws IOException {
        in = new MyScanner();
        solve();
        in.close();
    }

    private MyScanner in;

    public class MyScanner {
        private BufferedReader br;
        private StringTokenizer st;

        public MyScanner() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public MyScanner(String fileTitle) throws IOException {
            this.br = new BufferedReader(new FileReader(fileTitle + ".in"));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return "-1";
                }
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public int[] nextIntArr(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        public void close() throws IOException {
            br.close();
        }
    }

    public static void main(String[] args) throws IOException {
        new Solution().run();
    }
}
