/*Ylesanne p2rineb 2004 a koolilaste informaatika olympiaadi l6ppvoorust.
 * On antud arvude jada (originaalis oli juttu lauam2ngust nagu ridakabe)
 * ja on vaja leida k6ige pikem vahe kahe arvu vahel, kus 1. arv on suurem
 * teisest arvust, st k6ik vahepealsed arvud peavad 1. arvust v2iksemad olema.
 */
#include <stdio.h>
#include <time.h>
#define MaxN 100
main(){
  int a[MaxN];
  int i,j,k;
  int alg, lopp, on, e, v;
  clock_t cl1, cl2;                  // Aeg, mis on kulunud programmi käivitamisest. Samuti longint. Täpsus 1/100 sekundit.
  srand(time(0));
  for (i=0; i<MaxN; i++) {
     a[i]=rand()%100; //  Juhuslikud arvud 0 .. 99
  }
//  for (i=0; i<MaxN; i++) {
//     printf("%d ",a[i]);
//     }
  cl1=clock();                       // Programmi käivitamisest kulunud aja küsimine (kooskõlas clock_t-ga)
  lopp=0;
  alg=0;
  for (i=0; i<MaxN-1; i++) {
          e=i; v=i;      //Fikseerime 1. ja viimase
          while (v<MaxN) {           // Ja hakkame viimast edasi nihutama kui esimesest väiksem arv seda lubab.
               if (a[e]>a[v]) {
                  v++;
               }
               else {
                    if (lopp-alg<v-e) {
                         lopp=v; alg=e;
                    }
                    e=v;
                    v++;
               }
          }
          if (lopp-alg<v-e) {
               lopp=v; alg=e;
          }
  }
  cl2=clock();                       // Programmi käivitamisest kulunud aja küsimine (kooskõlas clock_t-ga)
  printf("\nRuutkeerukus. Arve %d\n",MaxN);
  printf("Ajavahe clockiga %ld\n",cl2-cl1);        // kahe clock_t vahe saab niisama lahutades
  printf("Pikim vahe on algusega %d ja lopuga %d",alg,lopp);
  getch();
}