#include #include #define MaxN 100000 int N; struct dvojice { int pozice, hodnota; } S[MaxN]; int M; int vystup_hodnota[MaxN]; int vystup_diference[MaxN]; unsigned int random; // Pro podrobnosti o generování náhodných čísel // si vyhledejte například lineární kongruentní generátor int nahodne_cislo() { return random = (random + 1000000007) % 22031993; } void prohod(int p, int q) { struct dvojice tmp = S[p]; S[p] = S[q]; S[q] = tmp; } // Porovnání prvků S[p] a S[q] v lexikografickém uspořádání bool mensi(int p, int q) { if (S[p].hodnota != S[q].hodnota) return S[p].hodnota < S[q].hodnota; return S[p].pozice < S[q].pozice; } // Setřidění prvků S[l], S[l+1],...,S[r-1] void quicksort(int l, int r) { if (l < r) { int pivot = l + nahodne_cislo() % (r - l); prohod(pivot, l); pivot = l; int hranice = l; for (int i = l + 1; i < r; i++) { if (mensi(i, pivot)) prohod(i, ++hranice); } prohod(pivot, hranice); quicksort(l, hranice); quicksort(hranice + 1, r); } } int main() { random = 0xDEADBEEF; scanf("%d", &N); for (int i = 0; i < N; i++) { S[i].pozice = i; scanf("%d", &S[i].hodnota); } quicksort(0, N); for (int i = 0; i < N; i++) { // H je aktuální prvek, jehož aritmetický výskyt kontrolujeme int H = S[i].hodnota; // Ošetříme zvlášť případ, kdy má prvek pouze jediný výskyt // a kdy násobný if (i == N - 1 || S[i+1].hodnota != H) { vystup_diference[M] = 0; vystup_hodnota[M] = H; M++; } else { int d = S[i+1].pozice - S[i].pozice; bool aritmeticky_vyskyt = true; while (i < N - 1 && S[i+1].hodnota == H) { if (S[i+1].pozice - S[i].pozice != d) aritmeticky_vyskyt = false; i++; } if (aritmeticky_vyskyt) { vystup_hodnota[M] = H; vystup_diference[M] = d; M++; } } } printf("%d\n", M); for (int i = 0; i < M; i++) printf("%d %d\n", vystup_hodnota[i], vystup_diference[i]); return 0; }