/*Ylesanne p2rineb 2004 a koolilaste informaatika olympiaadi l6ppvoorust.
 * On antud arvude jada 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. Originaalis oli juttu lauam2ngust ridakabe
 * ja küsiti kui kaugele saab nupuga hüpata, kui nupp "ületab" vaid endast
 * madalamaid nuppe.
 */
#include <stdio.h>
#include <time.h>
#define MaxN 100
main(){
  int a[MaxN];
  int i,j,k;
  int alg, lopp, on, e, v;
  time_t now, now1;                  // Aeg tegelikult tavaline long integer
  struct tm *time_now, *time_now1;   // Struktuur, mis kirjeldatud aja "osade" hoidmiseks
  srand(time(0));                    // Juhuslike arvude generaatori algväärtustamine
  for (i=0; i<MaxN; i++) {
     a[i]=rand()%100; //  Juhuslikud arvud 0 .. 99
  }
  for (i=0; i<MaxN; i++) {
     printf("%d ",a[i]);
     }
  now = time(0);
  time_now = localtime(&now);
  lopp=0;
  alg=0;         // Seni leitud pikima vahe algus ja lõpp
  e=0; v=0;      // Uue vahe kontrollimiseks esimene ja viimane indeks
  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;
  }
  now1 = time(0);
  time_now1 = localtime(&now1);
  printf("\nLineaarne keerukus. Arve %d\n",MaxN);
  printf("Algus %d\n",time_now->tm_sec);
  printf("Lõpp %d\n",time_now1->tm_sec);
  printf("Kestvus %d\n",difftime(now1,now));
  printf("Pikim vahe on algusega %d ja lopuga %d",alg,lopp);

}