// Contoh Bab 08: dua rencana untuk soal yang sama.
//
// Soal: diberikan n bilangan, cetak selisih terkecil antara dua bilangan
// yang berbeda posisi.
//
// Cara 1: periksa semua pasangan        -> sekitar n*n/2 langkah
// Cara 2: urutkan lalu periksa tetangga -> sekitar n log n langkah
//
// Compile:  g++ -std=c++17 -O2 -o selisih exercises/08/02-selisih-terkecil.cpp
// Jalankan: ./selisih
// Contoh masukan: 2000   (lalu coba 200000; cara 1 tidak akan selesai)

#include <iostream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;

const int MAKS = 200005;
int a[MAKS];

int cara_semua_pasangan(int n) {
    int terkecil = 2000000000;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            terkecil = min(terkecil, abs(a[i] - a[j]));
    return terkecil;
}

int cara_urutkan(int n) {
    sort(a, a + n);
    int terkecil = 2000000000;
    for (int i = 1; i < n; i++)
        terkecil = min(terkecil, a[i] - a[i - 1]);
    return terkecil;
}

int main() {
    int n;
    cin >> n;

    // Data uji dibuat sendiri supaya tidak perlu mengetik n angka.
    for (int i = 0; i < n; i++) a[i] = (int)((1LL * i * 7919) % 1000000007);

    clock_t t0 = clock();
    int hasil1 = cara_semua_pasangan(n);
    double detik1 = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();
    int hasil2 = cara_urutkan(n);
    double detik2 = (double)(clock() - t0) / CLOCKS_PER_SEC;

    cout << "semua pasangan: " << hasil1 << " (" << detik1 << " detik)\n";
    cout << "urutkan dulu  : " << hasil2 << " (" << detik2 << " detik)\n";
    return 0;
}