Armenian SPOJ

Ձեռքսեղմումներ

Ձեռնարկությունում աշխատում են n հոգի։ Նրանք համարակալված են 1-ից n թվերով։ Նրանք աշխատանքի վայր են գալիս իրենց համարների աճման կարգով։ Ամեն նոր եկողը ձեռքով բարևում է մինչ այդ եկած իր ընկերներին, հնարավոր է մինչ այդ եկածները, բոլորն իր ընկերներն են, հնարավոր է, ոչ մեկն իր ընկերը չէ։
Հայտնի է, թե մտնողներից յուրաքանչյուրը քանի հոգու հետ ձեռք սեղմեց։ Արդյունքում յուրաքանչյուր աշխատող ինչ-որ քանակությամբ մարդկանց ձեռք սեղմեց։ Հարկավոր է հաշվել մաքսիմալ հնարավոր քանակով ընկերներ ունեցող աշխատողի ընկերների քանակը, և մինիմալ հնարավոր քանակով ընկերներ ունեցող աշխատողի ընկերների քանակը։

Մուտքային տվյալներ

Առաջին տողում տրված է աշխատողների n (2 ≤ n ≤ 200 000) քանակը։ Երկրորդ տողում տրված են իրարից մեկական բացատանիշով անջատված n թվեր, որոնցից i-րդը ցույց է տալիս, թե i համարի աշխատողը, ներս մտնելիս, քանի ձեռքսեղմում է արել։

Ելքային տվյալներ

Հարկավոր է արտածել երկու թիվ՝ հնարավոր մաքսիմալ և մինիմալ քանակները։

Օրինակներ

Մուտք
Ելք
5 0 0 1 1 1
3 0
5 0 0 2 2 3
4 1

Բացատրություն

Առաջին օրինակում 3,4,5 աշխատակիցները կարող են սեղմել 1 աշխատակցի ձեռքը և չսեղմել 2 աշխատակցի ձեռքը։
Երկրորդ օրինակում 4,5 աշխատակիցները կարող են սեղմել 3 աշխատակցի ձեռքը, կստացվի, որ 3 աշխատակիցը 4 հոգու հետ ձեռք է սեղմել։ Վատագույն դեպքում 1,2 աշխատակիցները մեկ ձեռքսեղմում կունենա։
 

Constraints

Time limit: 0.2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue