Ձեռքսեղմումներ
Ձեռնարկությունում աշխատում են 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