import java.util.Scanner;

public class Viimeinen {

    public static Scanner lukija = new Scanner(System.in);

    public static void main(String[] args) {
        System.out.print("Kuinka monta? ");
        int n = lukija.nextInt();
        int voittaja = viimeinen(n);
        System.out.println("Voittaja: " + voittaja);

    }

    public static int viimeinen(int n) {
        Rinki rinki = new Rinki();

        for (int i = 1; i <= n; i++) {
            rinki.insert(i);
        }

        Rinkisolmu aloitus = rinki.getAlku();

        while(rinki.getKoko() > 1) {
            aloitus = rinki.delete(aloitus);
        }

        return rinki.getAlku().getKey();
    }
}

class Rinki {

    Rinkisolmu alku;
    Rinkisolmu loppu;
    int koko;

    void insert(int key) {
        Rinkisolmu uusi = new Rinkisolmu(key);
        koko++;

        if (alku == null) {
            alku = uusi;
            loppu = alku;
            alku.next = loppu;
            loppu.next = alku;
            return;
        }

        loppu.next = uusi;
        loppu = uusi;
        loppu.next = alku;
    }

    Rinkisolmu delete(Rinkisolmu edel) {
        koko--;

        if(edel == loppu) {
            alku = alku.next;
            loppu.next = alku;
            return alku;
        }
        if(edel.next == loppu) {
            loppu = edel;
            loppu.next = alku;
            return alku;
        }
        Rinkisolmu pois = edel.next;
        edel.next = pois.next;
        return edel.next;


    }

    int getKoko() {
        return koko;
    }

    Rinkisolmu getAlku() {
        return alku;
    }

}

class Rinkisolmu {

    int key;
    Rinkisolmu next;

    Rinkisolmu(int k) {
        key = k;
    }

    Rinkisolmu getNext() {
        return next;
    }

    int getKey() {
        return key;
    }
}