Description

Let's say you're a data analyst at a hospital with a database containing patient age information. You've been tasked with designing an algorithm to find the median age of the patients in O(n) time complexity.

 

Your goal is to devise an algorithm that efficiently finds the median age among these ages and maintains a time complexity of O(n) even with a substantial amount of data.

 

In this context, the median is the number that appears in the middle when all ages are arranged in ascending order. For an odd number of data points, the median is the exact middle number after sorting. For an even number of data points, the median is the floor of the average of the two middle numbers.

 

Hint:

The worst case of quicksort is O(n²) and there is worst case in the testcase.

How to avoid it?

 

Note: Among STL data structure, only vector is allowed to use. To get full score, you need to find out a O(n) solution.

* sorting functions, like sort in <algorithm> or qsort in <stdlib.h>, which can directly sort the array are prohibited

(You can import <algorithm> or <stdlib.h> but don't use sort or qsort function)

* Data structure like <set>, <priority_queue>, <ordered_set>, <list>, are also prohibited

* The random function which can generate random value is allowed.

Random function tutorial:

https://www.geeksforgeeks.org/rand-and-srand-in-ccpp/

Input

The first line has an integer number, N, indicates there are N patients in the hospital

The second line contains N unique unsorted integer ages of paitents.

 

Constraint:

0 < N < 10000000

0 <= ages <= 2^31 - 1

Output

Print the median age of the patients

Note that you need to print ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Charlotte can now write many Arabic numerals, so her teacher gave her an advanced assignment.

First, given an array A of N numbers and Q queries.

Each query consists of two numbers L and R. For each query, Charlotte needs to answer how many i satisfy L ≤ A[i] ≤ R in the given array A (where i is integer and 1 ≤ i ≤ N).

Please help Charlotte complete her homework.

Input

The first line contains two numbers N, Q (1 ≤ N ≤ 2 × 10⁵, 1 ≤ Q ≤ 2 × 10⁵).

The second line contains N numbers representing A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ 10⁸).

The next Q lines each contain two numbers L and R (guaranteed that 1 ≤ L ≤ R ≤ 10⁸).

Output

Output Q lines, each representing the answer to the corresponding query.

Please add a newline('\n') at the end of each line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given n 2D points, select k points such that the value of max(x_¹, x₂, ..., x_k) + max(y₁, y₂, ..., y_k) is minimized. Here, (x₁, y₁), (x₂, y₂), ..., (x_k, y_k) are the coordinates of the selected k points.

Input

The first line contains two positive integers n and k.
The next n lines each contain two integers, representing the x and y coordinates of the n 2D points.

Constrain

• 0 < k ≤ n ≤ 10⁶
• 0 < x₁, x₂, ..., x_n ≤ 10⁶
• 0 < y₁, y₂, ..., y_n ≤ 10⁶

Output

Output the minimum value of max(x_¹, x₂, ..., x_k) + max(y₁, y₂, ..., y_k).

Remember to print a ‘\n’ at the end of the output.

HINT

Select points (1, 6), (4, 8), and (5, 9) such that max(1, 4, 5) + max(6, 8, 9) = 14. This is the optimal selection.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given an array with length n a₁, a₂, ... , a_n. Answer the number of pairs (i, j) satisfying:

• 1 <= i < j <= n
• a_i > a_j

Input

The first line contains one integer n, the length of array. 

The next line contains n integers a₁, a₂, ... , a_n.

Constrain

• 1 <= n <= 10⁶
• | a_i | <= 10¹⁶, i = 1, 2, ... , n

Output

Output one integer, the number of pairs that satisfy the condition above.

Remember to print a ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss