문제
우리가 흔히 아는 노래에 나오는 울퉁불퉁 멋진 몸매에 빨간 옷을 입고 새콤달콤 향내 풍기는 멋쟁이 토마토는 주스도 되고 싶고, 케첩도 되고 싶고, 춤도 추고 싶다.
그러나 우리의 멋쟁이 토마토는 그저 케첩이 되고 싶다.
그러나 아무 멋쟁이 토마토나 케첩이 될 수 있는 것은 아니다.
멋쟁이 토마토를 케첩으로 만들어 줄 수 있는 멋쟁이 케첩 회사는 소비자들의 트렌드에 민감하다.
매주 소비자 설문조사를 통해 어느 정도의 숙성도의 토마토를 가장 선호하는지 파악하여 해당 숙성도의 토마토만을 케첩으로 만든다.
멋쟁이 토마토들은 자신의 멋짐을 뽐내기 위하여 일렬로 나란히 서 있다.
이때, 일정 구간을 선정해 그 주의 설문조사를 통해 알아낸 선호 숙성도 구간에 해당하는 멋쟁이 토마토가 몇개인지를 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에 멋쟁이 토마토들의 개수인 N과 질의의 수 M이 공백을 기준으로 입력된다. (1 <= N, M <= 100,000)
두 번째 줄에는 멋쟁이 토마토의 숙성도 A1, A2, ..., AN이 주어진다. (1 <= Ai <= 109)
세 번째 줄부터 M줄에 걸쳐 질의가 입력되는데, 각 질의는 토마토를 선별할 구간의 시작점 S, 끝점 E, 선호 숙성도 최솟값 L, 선호 숙성도 최댓값 H이 공백을 기준으로 입력된다. (1 <= S <= E <= N, 1 <= L <= H <= 109)
출력
M줄에 걸쳐 각 질의마다 한 줄에 하나씩 캐첩이 될 수 있는 멋쟁이 토마토의 개수를 출력하시오.
예제1
입력
53
12345
1524
2415
2435
출력
3
3
2
출처
@klee