/*
public class Kierrokset {
    int laske(int[] t) {
        int kierrokset = 1;
        boolean t2[] = new boolean[t.length+2];

        for (int i=0; i < t.length; i++) {
            if (t2[t[i]+1] == true) kierrokset++;

            t2[t[i]] = true;
        }
        return kierrokset;
    }
}*/

public class Kierrokset {
    int laske(int[] t) {

        // Ideana on luoda aputaulukko, jossa kohta[x] ilmaisee, missä kohdassa
        // luku x esiintyy taulukossa. Tämän muodostaminen vie aikaa O(n). Tämän
        // jälkeen käydään läpi luvut keräysjärjestyksessä. Aina jos kerättävä
        // luku esiintyy taulukossa aiemmin kuin viimeksi kerätty luku, täytyy
        // aloittaa uusi kierros.

        int n = t.length;
        int[] kohta = new int[n+1];
        for (int i = 0; i < n; i++) {
            kohta[t[i]] = i;
        }
        int tulos = 1;
        for (int i = 2; i <= n; i++) {
            if (kohta[i] < kohta[i-1]) tulos++;
        }
        return tulos;
    }
}