help needed
closed account (9LzTpfjN)
Raja only participates in contests and does not upsolve, but he claims that he has been upsolving. Chef wants to test if he is really improving, so he asks Raja to solve the following problem.
The median of a sequence of numbers is computed in the following way:
sort the sequence in non-decreasing order
if the number of elements of this sequence is odd, the median is its middle element
if the number of elements is even, the median is the average (arithmetic mean) of its two middle elements
For example, the median of [1,3,2] is 2 and the median of [2,3,3,2] is (2+3)/2=5/2.
You are given a sequence A1,A2,…,AN. Let's call a subsequence Ai1,Ai2,…,Aik (for any k>0, 1≤i1<i2<…<ik≤N) good if the median of this subsequence is an element of this subsequence. Find the number of good subsequences. Since this number may be large, compute it modulo 1000000007 (109+7).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer — the number of good subsequences modulo 109+7.
Constraints
1≤T≤30
1≤N≤1,000
1≤Ai≤2N for each valid i
Subtasks
Subtask #1 (5 points): A is a permutation of integers 1 through N
Subtask #2 (25 points): 1≤N≤100
Subtask #3 (70 points): original constraints
Example Input
1
3
2 3 2
Example Output
5
Explanation
Example case 1: The good subsequences are [2], [3], [2], [2,2], [2,3,2]
Can somebody help me in this question.please.
The median of a sequence of numbers is computed in the following way:
sort the sequence in non-decreasing order
if the number of elements of this sequence is odd, the median is its middle element
if the number of elements is even, the median is the average (arithmetic mean) of its two middle elements
For example, the median of [1,3,2] is 2 and the median of [2,3,3,2] is (2+3)/2=5/2.
You are given a sequence A1,A2,…,AN. Let's call a subsequence Ai1,Ai2,…,Aik (for any k>0, 1≤i1<i2<…<ik≤N) good if the median of this subsequence is an element of this subsequence. Find the number of good subsequences. Since this number may be large, compute it modulo 1000000007 (109+7).
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer — the number of good subsequences modulo 109+7.
Constraints
1≤T≤30
1≤N≤1,000
1≤Ai≤2N for each valid i
Subtasks
Subtask #1 (5 points): A is a permutation of integers 1 through N
Subtask #2 (25 points): 1≤N≤100
Subtask #3 (70 points): original constraints
Example Input
1
3
2 3 2
Example Output
5
Explanation
Example case 1: The good subsequences are [2], [3], [2], [2,2], [2,3,2]
Can somebody help me in this question.please.
closed account (jLCX216C)
Please First you share the code I would definitely share the code
BTW I have given you the complete idea for HMAPPY in another post
BTW I have given you the complete idea for HMAPPY in another post
closed account (jLCX216C)
I am using the same but getting WA that's why I am telling you to share code
Topic archived. No new replies allowed.