26168번 - 배열 전체 탐색하기 서브태스크

문제

크기 n인 정수형 배열 A가 주어진다. 배열 A의 원소는 A[0], A[1], ... , A[n-1]이다. 배열 A에는 같은 값을 갖는 원소가 여러 개 존재할 수 있다. 배열 A에 대한 m개의 질의가 저장된 배열 B가 주어진다. 배열 B에 저장된 m개의 질의는 아래 세 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2, 세 번째가 유형 3이다.

• 1 k: 배열 A의 원소 중 k보다 크거나 같은 원소의 개수를 출력한다.
• 2 k: 배열 A의 원소 중 k보다 큰 원소의 개수를 출력한다.
• 3 i j: 배열 A의 원소 중 i보다 크거나 같고 j보다 작거나 같은 원소의 개수를 출력한다.

배열 B에 저장된 첫 번째 질의부터 m번째 질의까지 순서대로 처리하면서 질의 결과를 출력하자.

입력

첫 번째 줄에 n과 m이 공백을 사이에 두고 순서대로 주어진다.

두 번째 줄에 배열 A의 원소 A[0], A[1], ... , A[n-1]이 공백을 사이에 두고 순서대로 주어진다.

세 번째 줄부터 m개의 줄에 걸쳐 배열 B에 저장된 m개의 질의가 순서대로 주어진다. 한 줄에 하나의 질의를 나타내는 정수가 공백을 사이에 두고 순서대로 주어진다.

출력

첫 번째 줄부터 질의 결과를 순서대로 한 줄씩 출력한다.

제한

• 1 ≤ n, m ≤ 100,000
• 1 ≤ A[i] ≤ 10¹⁸ (0≤ i ≤ n - 1)
• 1 ≤ i ≤ j ≤ 10¹⁸
• 1 ≤ k ≤ 10¹⁸

서브태스크

힌트