SPOJ in Armenian

Պետք է կառուցել արգելք մրցումների համար, որը կազմված լինի 1,2,...,N բարձրություններով հարթակներից, որոնք տեղադրվում են մի գծի երկարությամբ, կամայական հերթականությամբ: Երկու հաջորդական հարթակների միջև անցման դժվարությունը հավասար է այդ հարթակների բարձրությունների տարբերությանը, այսինքն, եթե մեկի բարձրությունը հավասար է H_i, իսկ մյուսինը՝ H_i+1, ապա նրանց միջև անցման դժվարությունը‎ կլինի | H_i+1 – H_i |: ‎Ամբողջ արգելքի անցման դժվարությունը բոլոր հարևան հարթակների անցման դժվարությունների գումարն է:

Օրինակ՝ 1 2 4 3 5 դասավորության դեպքում այն կլինի |2-1|+|4-2|+|3-4|+|5-3|=6:

Պետք է գտնել, թե ամենաշատը ինչ անցման դժվարությամբ արգելք կարելի է կառուցել:

Մուտքը

Մուտքում տրված է մի  N բնական թիվ (2<=N<=1000000000)։

Ելքը

Պատասխանը պետք է լինի մի ամբողջ թիվ՝ թե տրված N-ի համար ամենաշատը ինչ անցման դժվարությամբ արգելք է հնարավոր կառուցել, և, քանի որ պատասխանը կարող է բավականին մեծ լինել, պետք է արտածել պատասխանը 9973–ի վրա բաժանելուց ստացվող մնացորդը:

Օրինակ

Մուտքը.
5

Ելքը.
11