#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N=10000000;
const int REP=100000000;

int A[N],R[N];

int main() {
  clock_t start,end;
  
  for (int i=0; i<N-1; i++)
    A[i]=i+1;
  A[N-1]=0;
  R[0]=0;

  for (int i=1; i<N; i++) {
    int r = rand() % i;
    R[i]=R[r];
    R[r]=i;
  };

  start = clock();
  int p=0;
  for (int i=0; i<REP; i++)
    p=A[p];
      
  end = clock();
  double time = (end - start) / (double)(CLOCKS_PER_SEC / 1000);
  cout << "time=" << time/1000 << endl;

  start = clock();
  
  p=0;
  for (int i=0; i<REP; i++)
    p=R[p];
      
  end = clock();
  time = (end - start) / (double)(CLOCKS_PER_SEC / 1000);
  cout << "time=" << time/1000 << endl;
};