Firehose

Στη γειτονιά σας υπάρχει ένας πολύ ασυνήθιστος δρόμος. Αυτός ο δρόμος σχηματίζει έναν τέλειο κύκλο, που η περιφέρεια του είναι ~1\;000\;000~. Στο δρόμο αυτό υπάρχουν ~H\;(1 \le H \le 1000)~ σπίτια. Η διεύθυνση κάθε σπιτιού είναι δεξιόστροφα, το μήκος τόξου από το βορειότερο σημείο του κύκλου. H διεύθυνση του σπιτιού στο βορειότερο σημείο του κύκλου είναι ~0~.

Υπάρχουν επίσης ειδικοί πυροσβεστικοί σωλήνες που ακολουθούν την καμπύλη του δρόμου. Ωστόσο, επιθυμείτε να διατηρήσετε το μήκος του μακρύτερου πυροσβεστικού σωλήνα που χρειάζεστε στο ελάχιστο δυνατό.

Ο στόχος σας είναι να τοποθετήσετε ~k\;(1 \le k \le 1000)~ πυροσβεστικούς κρουνούς σε αυτόν τον δρόμο, έτσι ώστε το μέγιστο μήκος πυροσβεστικού σωλήνα που θα απαιτείται για τη σύνδεση ενός σπιτιού με έναν πυροσβεστικό κρουνό να είναι όσο το δυνατόν μικρότερο.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ακέραιο ~H~, τον αριθμό των σπιτιών. Οι επόμενες ~H~ γραμμές θα περιέχουν έναν ακέραιο αριθμό η καθεμία, που θα αντιστοιχεί στη διεύθυνση του συγκεκριμένου σπιτιού και κάθε διεύθυνση σπιτιού θα είναι τουλάχιστον ~0~ και μικρότερη από ~1\;000\;000~. Η γραμμή ~H + 2~, θα περιέχει τον αριθμό ~k~, ο οποίος είναι ο αριθμός των πυροσβεστικών κρουνών που μπορούν να τοποθετηθούν γύρω στον κύκλο. Σημειώστε ότι ένας πυροσβεστικός κρουνός μπορεί να τοποθετηθεί στην ίδια θέση με ένα σπίτι. Μπορείτε να υποθέσετε ότι δεν υπάρχουν δύο σπίτια στην ίδια διεύθυνση. Σημείωση: για τουλάχιστον το ~40%~ των βαθμών αυτού του ερωτήματος, ~H \le 10~.

Έξοδος

Σε μία γραμμή, εξάγετε το μήκος του πυροσβεστικού σωλήνα που απαιτείται ώστε κάθε σπίτι να μπορεί να συνδεθεί με τον πλησιέστερο πυροσβεστικό κρουνό με αυτό το μήκος σωλήνα.

Παράδειγμα

input

4
0
67000
68000
77000
2

output

5000