301861: CF352B. Jeff and Periods

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Jeff and Periods

题意翻译

给定一个长度为 $n$ 的序列 $a_1,a_2,a_3,\dots,a_n$($1\le a_i\le 10^5$),你需要找出一些 $x$,满足: - $x$ 在序列 $a$ 中出现; - 将 $x$ 在 $a$ 中出现的所有所有位置从小到大排序为一个序列 $b_1,b_2,b_3,\dots,b_m$,($m$ 为 $x$ 在 $a$ 中出现的位置),这一个序列是等差序列(即 $b_2-b_1=b_3-b_2=\dots=b_m-b_{m-1}$)。 输出所有满足条件的 $x$ 与对应的序列 $b$ 的相邻两项的差的绝对值。 Translated by Rosmarinus.

题目描述

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.

输入输出格式

输入格式


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.

输出格式


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 $ .

输入输出样例

输入样例 #1

1
2

输出样例 #1

1
2 0

输入样例 #2

8
1 2 1 3 1 2 1 5

输出样例 #2

4
1 2
2 4
3 0
5 0

说明

In the first test $ 2 $ occurs exactly once in the sequence, ergo $ p_{2}=0 $ .

Input

题意翻译

给定一个长度为 $n$ 的序列 $a_1,a_2,a_3,\dots,a_n$($1\le a_i\le 10^5$),你需要找出一些 $x$,满足: - $x$ 在序列 $a$ 中出现; - 将 $x$ 在 $a$ 中出现的所有所有位置从小到大排序为一个序列 $b_1,b_2,b_3,\dots,b_m$,($m$ 为 $x$ 在 $a$ 中出现的位置),这一个序列是等差序列(即 $b_2-b_1=b_3-b_2=\dots=b_m-b_{m-1}$)。 输出所有满足条件的 $x$ 与对应的序列 $b$ 的相邻两项的差的绝对值。 Translated by Rosmarinus.

加入题单

上一题 下一题 算法标签: