Rezolvare PBinfo #1963

Șcuțu este un mare matematician. Într-o seară acesta a inventat operația ∆. Operația ∆ se aplică pe 2 numere naturale, astfel:

• 290 ∆ 345 = 290345
• 21 ∆ 12 = 2112
• 456 ∆ 0 = 4560

Mygo și Seba sunt la rândul lor foarte buni informaticieni. Aceștia au un vector A cu N elemente, numere naturale, indexate de la 1. Ei vor construi un nou vector V, acesta la rândul său indexat de la 1, ce conține fiecare valoare A[i] ∆ A[j] (1 ≤ i, j ≤ N) pe care îl vor sorta crescător.

Cerința

Acum Șcuțu le va pune celor 2 câte două întrebări:

1. Câte valori din V sunt mai mici sau egale cu X ?
2. Pentru X dat, ce valoare se află pe poziția X ?

Să se răspundă la cele 2 întrebări.

Date de intrare

Fișierul de intrare op.in conține pe prima linie numărul t, având valoarea 1 sau 2, reprezentând tipul întrebării la care se cere răspunsul. Pe a doua linie linie se află numărul N și X iar pe a treia linie se vor afla N numere naturale nenule, reprezentând valorile vectorului A.

Date de ieșire

Fișierul de ieșire op.out va conține pe prima linie numărul S, reprezentând răspunsul întrebării.

Restricții și precizări

• 1 ≤ N ≤ 100.000
• numerele de pe a treia linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
• t = 1 pentru 30p

Exemplu:

op.in

1
3 23
1 2 4

op.out

5

Explicație

V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Sunt 5 numere mai mici decât 23.

op.in

2
3 6
1 2 4

op.out

24

Explicație

V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Pe poziția 6 se află numărul 24.