Algo lab/running times

This is part of ske algo lab

Lab descriptions

• Work on this lab sheet.
• Write quadratic-time solutions to the following two problems.
• Download fast solutions.
• Measure their running times using provided test data and compare them.

Task 1: Closest pairs

Task statement

You are given a list of n integers. You want to find the minimum difference between pairs of these integers.

Input

• First line: integer n (n is at most 100,000)
• Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)

Output

• One line: the minimum difference between pairs of these integers.

Example

Input:

5
1
50
4
13
25

Output:

3

Your job

• Template for quadratic solution closest-slow-template.cpp
• Fast solution closest-fast.cpp
• Test data: see below

Task 2: Sorting

Task statement

You are given a list of n integers. You want to sort them in an increasing order.

Input

• First line: integer n (n is at most 100,000)
• Next n lines: each line contains one integer (ranging from 1 to 1,000,000,000)

Output

• n lines: the sorted list of integers

Example

Input:

5
1
50
4
13
25

Output:

1
4
13
25
50

Your job

• Template for quadratic solution sort-slow-template.cpp
• Fast solution sort-fast.cpp
• Test data: see below