시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

There are N (software) engineers in PT Untung Pasti Bahagia (UPB) whose numbers are from 1 to N. As their manager, Andi knows those engineers very well and has assigned a potential score to each of them where Pi represents the ith engineer’s potential.

Once in a while, a project offer comes to UPB. As a manager, Andi evaluates the project proposal and determines that he will need a team of at least one engineer that has an average potential score of at least S. To avoid any issue due to instability of the potential scores, Andi wants each engineer in the selected team to have a potential score between A and B, inclusive. Andi also (naively) believes that the more engineers he has in a team, the better the project will run.

Due to a weird company policy, the project can only be run by a team of engineers whose number is between L and R, inclusive. In other words, Andi has to select as many engineers as possible whose numbers are between L and R (inclusive) and whose potential scores are between A and B (inclusive) such that the average potential score of the selected engineers is at least S.

There are Q incoming projects, each having their own L, R, A, B, and S values. For each project, help Andi to determine the maximum number of engineers that can join the team for the project, or determine if there is no solution.

입력

Input begins with a line containing an integer: N (1 ≤ N ≤ 200 000) representing the number of engineers in UPB. The next line contains N integers: Pi (1 ≤ Pi ≤ 200 000) representing the potential score of the engineers. The next line contains an integer: Q (1 ≤ Q ≤ 200 000) representing the number of incoming projects. The next Q lines, each contains five integers: L R A B S (1 ≤ L ≤ R ≤ N; 1 ≤ A ≤ B ≤ 200 000; 1 ≤ S ≤ 200 000) representing the number range and the potential score range in which Andi can select the engineers from and the minimum average potential score for the selected team, respectively.

출력

For each incoming project in the same order as input, output in a line an integer representing the maximum number of engineers that can be selected for the respective project, or output 0 if there is no solution.

예제 입력 1

6
1 2 3 4 5 6
4
1 6 1 6 1
1 6 1 6 5
1 6 5 6 5
1 3 4 5 1

예제 출력 1

6
3
2
0
  • For the 1st incoming project, all engineers can be selected and the minimum average potential score is 1. Therefore, Andi can select all engineers as each of them has a potential score of at least 1. The average potential score if all engineers are selected is 3.5.
  • For the 2nd incoming project, all engineers can be selected but the minimum average potential score is 5. Therefore, Andi should select engineer number 4, 5, and 6, with potential scores of {4, 5, 6} and an average potential score of 5.
  • For the 3rd incoming project, only the last two engineers (number 5 and 6) can be selected and the minimum average potential score is 5. Therefore, Andi can simply select those two engineers with potential scores of {5, 6} and an average potential score of 5.5.
  • For the 4th incoming project, there are no engineers whose number is between 1 and 3 that has a potential score between 4 and 5. Therefore, there is no solution.

예제 입력 2

5
20 50 70 30 80
4
1 3 50 60 40
1 5 30 40 50
2 4 30 70 50
1 4 10 80 55

예제 출력 2

1
0
3
2