Վերին սահման (Upper bound)
Տրված է աճման կարգով դասավորված n ամբողջ թվերից կազմված զանգված, և ձեզ խնդրում են պատասխանել q հարցումների: Յուրաքանչյուր հարցում ձևակերպված է հետևյալ կերպ. «Ո՞րն է առաջին թվը, որը մեծ է x-ից տվյալ ցուցակում»։
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n (2 ≤ n ≤ ) և q (1 ≤ q ≤ )։
Մուտքի հաջորդ տողում տրված են n ամբողջ թվեր ( ≤ ≤ ) աճման կարգով։
Մուտքի վերջին տողում տրված են q հարցումներ ( ≤ < )։
Ելք
Ծրագիրը պետք է տպի q տող։ Յուրաքանչյուր տողում` համապատասխան հարցման պատասխանը։
Օրինակ
Մուտք | Ելք |
|---|---|
6 3 2 7 9 10 20 30 8 20 1 | 9 30 2 |
Հուշում
Երկուական որոնման (Binary Search) դասական իրականացման դեպքում օգտագործվում է [l; r) միջակայքը, որտեղ l-ը ներառված է, իսկ r-ը՝ ոչ։ Որոշ դեպքերում, սակայն, կարող է պահանջվել (l; r] տարբերակը՝ ներառելով r-ը, իսկ l-ը՝ ոչ։ Սա կպահանջի փոփոխություններ l, r և mid արժեքները հաշվարկի մեջ։
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB