A. Аялагчийн асуудал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Иахуб аялагчдыг шүтэн биширдэг. Тэр өөрөө аялагч болохыг хүсдэг ба нэг аялал төлөвлөсөн. Иахубын очихыг хүсч буй шулуун зам дээр байрласан $n$ зогсоол байна. Иахуб аялалаа 0 километрээс эхэлнэ. $n$ зогсоолуудыг эерэг бүхэл тоон $a_{1}$, $a_{2}$, ..., $a_{n}$ дарааллаар тодорхойлно. $a_{k}$ тоо нь $k$-р зогсоол эхлэх цэгээс $a_{k}$ зайд байрлана гэдгийг илэрхийлнэ. Ямар ч хоёр зогсоол нэг байрлалд байрлахгүй.

Иахуб зогсоол бүр дээр нэг удаа л очихыг хүсч байна. Иахуб үнэхээр тэр цэг дээр очиж зочлохыг хүсч буй учраас зогсоолоор дайрч өнгөрөхийг очсонд тооцохгүй. Мөн Иахуб өөрийн сүүлчийн зогсоол дээрээ оччихоод 0 километрруу буцахгүй ба аялалаа сүүлийн зогсоол дээрээ дуусгана.

$x$ километр дээр байрласан зогсоол болон $y$ километр дээр байрласан зогсоолын хоорондох зай нь $|x - y|$ километр байна. Бид зогсоолуудруу очих дарааллыг маршрут гэнэ. Иахуб зогсоолуудад дурын дарааллаар очиж болох ба тэр $n$ зогсоолуудад очих явцдаа нэг зогсоолд нэгээс олон очихгүй.

Иахуб цаасан дээр бүх боломжит маршрутыг бичиж эхлэсэн ба тус бүрийнх нь хувьд алхах нийт зайгаа тэмдэглэв. Тэр маршрут сонгоод алхах дундаж километрийг мэдэхийг хүсч байна. Тэр бүх маршрутыг бичээд уйдсан учир таныг туслахыг хүсч байна.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 10^{5}$) байна. Дараагийн мөрөнд ялгаатай $n$ бүхэл тоо $a_{1}$, $a_{2}$, ..., $a_{n}$ ($1 ≤ a_{i} ≤ 10^{7}$) байна.

Гаралт

Олохыг хүсэж буй дундаж тоотой тэнцүү бутархайн хүртвэр, хуваарийг илэрхийлэх хоёр бүхэл тоог хэвлэ. Бутархай нь хураагдахгүй бутархай байх ёстой.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3
2 3 5
Гаралт
22 3

Тэмдэглэл

Боломжит 6 маршрутыг авч үзье:

  • [2, 3, 5]: нийт аялах зай: |2 - 0| + |3 - 2| + |5 - 3| = 5;
  • [2, 5, 3]: |2 - 0| + |5 - 2| + |3 - 5| = 7;
  • [3, 2, 5]: |3 - 0| + |2 - 3| + |5 - 2| = 7;
  • [3, 5, 2]: |3 - 0| + |5 - 3| + |2 - 5| = 8;
  • [5, 2, 3]: |5 - 0| + |2 - 5| + |3 - 2| = 9;
  • [5, 3, 2]: |5 - 0| + |3 - 5| + |2 - 3| = 8.

Дундаж аялах зай нь = = .

Сэтгэгдлүүдийг ачааллаж байна...