/* PREcondition: The data file contains integers (and white space), only.
                 It contains at least one integer.                           */

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <assert.h>

FILE        *fp;

#define notOccurred (-1)
#define True        (1)

long min(long a, long b) { return a < b ? a : b ; }

long max(long a, long b) { return a > b ? a : b ; }

long mod(long i, long m) /* PRE: m > 0 */
        { return (i >= 0) ? (i % m) : (m - 1 - (-i-1) % m) ; }
/* Don't need mod(,) IF your m/c implements % correctly,                 */
/* mathematically,  on -ve ints                                          */
/* e.g.       i : ... -5 -4 -3 -2 -1  0  1  2  3  4  5  6...
        i mod 4 : ...  3  0  1  2  3  0  1  2  3  0  1  2...             */



/* This is a "good enough" solution.  The dependence on `m' (range) can
   be reduced by using various techniques (feel free to do so),  but
   this program meets the spec'  -- csse, Monash U., .au, 4/2004         */


void find_interval(long range)
{        long value, mn, mx, left, right, bestLeft, bestRight, i,
             *lastPosition,          /* records positions of last occurrence */
             range1;
        range1 = range + 1; /* e.g. if range==2, {5,6,7} {-1,0,1} etc are OK */
        lastPosition = malloc( (range+1)*(sizeof(long)) );


        fscanf(fp, "%ld", &value);                  /* -- first (0-th) value */

        left = 0;  right = 0;                                  /* initialise */
        mn = value; mx = value;                                /* the */
        lastPosition[mod(value, range1)] = right;              /* state */
        bestLeft = left; bestRight = right;       /* -- best interval so far */


        while( fscanf(fp, "%ld", &value) != EOF )
        { /* INV: left..right is a valid interval (left-1..right is not),    */
          /*      values in left..right are >= mn and <= mx, mx-mn<=range,   */
          /*    bestLeft..bestRight is longest valid subinterval of 0..right */

                right++; /* 1, 2, ... */


                if( value > mx + range )            /* value is MUCH too big */
                { /* i.e. value-mx > range */
                        mn = value; mx = value; left = right; /* all cleared */
                }

                else if( value < mn - range )     /* value is MUCH too small */
                { /* i.e. mn-value > range */
                        mn = value; mx = value; left = right; /* all cleared */
                }

                else if( value > mn + range )     /* value is too big for mn */
                { /* make mn bigger and adjust left */

                        for( ; mn < value-range; mn++)
                           left = max(left, lastPosition[mod(mn, range1)]);
                        /* mn == value-range,  mn <= mx */
                        left++;       /* skip last too-small value */
                        while( lastPosition[mod(mn, range1)] == notOccurred )
                           mn++;
                        for(mx++; mx < value; mx++)
                           lastPosition[mod(mx, range1)] = notOccurred;
                }

                else if( value < mx-range )     /* value is too small for mx */
                { /* make mx smaller and adjust left */
                  /* (the "mirror image" of the previous case) */

                        for( ; mx > value+range; mx--)
                           left = max(left, lastPosition[mod(mx, range1)]);
                        /* mx == value+range,  mx >= mn */
                        left++;         /* skip last too-big value */
                        while( lastPosition[mod(mx, range1)] == notOccurred )
                           mx--;
                        for(mn--; mn > value; mn--)
                           lastPosition[mod(mn, range1)] = notOccurred;
                }

                else            /* value is just right, does not upset range */
                { /* left can stick, might have to adjust mn or mx slightly  */

                        if(value > mx) /* new, slightly bigger, mx */
                                for(mx++; mx < value; mx++)
                                    lastPosition[mod(mx, range1)] = notOccurred;
                                /* assert: mx == value */

                        else if(value < mn) /* new, slightly smaller, mn */
                                for(mn--; mn > value; mn--)
                                   lastPosition[mod(mn, range1)] = notOccurred;
                                /* assert: mn == value */
                }

                                    /* record position of last occurrence... */
                lastPosition[mod(value, range1)] = right; /* ...in all cases */


                if(right - left > bestRight - bestLeft)
                { /* ? lengthen your interval ?-) */
                        bestLeft = left;  bestRight = right;
                }

        }/*while*/

        printf("\n%ld  %ld  %ld\n",                 /* and the answer is ... */
               bestLeft, bestRight, bestRight-bestLeft+1 );

} /* find_interval */


int main(int argc, char *argv[])
{        long i, range; /* :-) */

        if (argc != 3)
        {       printf("usage:  longest m f\n");
                exit(0);
        }
        range = atol(argv[1]);
        if( range < 0 )
        {       printf("usage:  longest m f   -- where m >= 0\n");
                exit(0);
        }
        if ((fp = fopen(argv[2],"r")) == NULL)
        {       printf("File not found %s.\n", argv[2]);
                exit(0);
        }

        find_interval(range);

        fclose(fp);
        exit(0);
} /* main*/