საშობაო საჩუქრები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


შობის ღამეს, გრანდიოზულ საოჯახო ზეიმზე, საჩუქრების მომლოდინე ბავშვები ნაძვის ხის გარშემო იკრიბებიან. თითოეულ ბავშვს თითო საჩუქარი ეკუთვნის, თუმცა მათი ღირებულება განსხვავებულია. წრეზე განლაგებული ბავშვებიდან თითოეულს თავისი კუთვნილი საჩუქრის გარდა შეუძლია დაინახოს მხოლოდ მის გვერდზე მდგომი 2 ბავშვის საჩუქარი და, შესაბამისად, შეაფასოს მათი ღირებულება. იმ შემთხვევაში თუ რომელიმეს ღირებულება საკუთარი საჩუქრის ღირებულებას აღემატება, ბავშვს გული წყდება, ხოლო გულის დაწყვეტის ხარისხი საჩუქრების ღირებულებებს შორის სხვაობას უდრის. თქვენი მიზანია წრეზე განლაგებულ ბავშვებს საჩუქრები ისე გადაუნაწილოთ, რომ ბავშვებს შორის მაქსიმალური გულის დაწყვეტის ხარისხი იყოს მინიმალური (იგივე, რაც გვერდიგვერდ მდგომი ბავშვების საჩუქრების ღირებულებების მაქსიმალური სხვაობა იყოს მინიმალური).

შესატანი მონაცემები

·         პირველ ხაზზმე მოცემულია მთელი რიცხვი n - ბავშვების რაოდენობა

·         მეორე ხაზზე მოცემულია n ცალი მთელი რიცხვი p1, p2, ..., pn - საჩუქრების ღირებულებები

შეზღუდვები

·         2 ≤ n ≤ 105

·         1 ≤ pi ≤ 109

გამოსატანი მონაცემები

დაბეჭდეთ მხოლოდ ერთი მთელი რიცხვი - საჩუქრების ოპტიმალური გადანაწილების შემთხვევაში მაქსიმალური გულის დაწყვეტის ხარისხი.




მაგალითები

შესატანი მონაცემები
5 2 1 4 1 2 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

Note: ერთერთი ოპტიმალური გადანაწილება იქნება 2 1 1 2 4, სადაც მაქსიმალური გულის დაწყვეტის ხარისხი არის |4 – 2| = 2.