// Timestamp list update technique, BPW 1/24/04
// See Borodin & El-Yaniv, p. 17

#include <stdio.h>

main()
{
int n,key[50],recent[50],previous[50];
int x,y,t=0,i,j;
int recentHold,previousHold;

printf("Enter n\n");
scanf("%d",&n);
for (i=0;i<n;i++)
{
  key[i]=i;
  recent[i]=previous[i]=0;
}
printf("Enter requests -1 to terminate\n");
scanf("%d",&x);
while (x!=(-1))
{
  t++;
  if (x<0 || x>=n)
    exit(0);
  for (i=0;
       key[i]!=x;
       i++)
    ;
  printf("partial cost is %d\n",i);
  if (recent[i]==0)
    recent[i]=t;
  else
  {
    previous[i]=recent[i];
    recent[i]=t;
    for (y=0;
      y<i && previous[y]>previous[i];
      y++)
      ;
    if (y<i)
    {
      recentHold=recent[i];
      previousHold=previous[i];
      for (j=i;j>y;j--)
      {
        key[j]=key[j-1];
        recent[j]=recent[j-1];
        previous[j]=previous[j-1];
      }
      key[y]=x;
      recent[y]=recentHold;
      previous[y]=previousHold;
    }
  }
  printf("key recent previous (t=%d)\n",t);
  for (i=0;i<n;i++)
    printf("%2d   %3d   %3d\n",key[i],recent[i],previous[i]);
  scanf("%d",&x);
}
}