SK_001 - Rightful Distribution
Akash , the director of the famous Timus Coaching Institute was very happy after the results of the Entrance Examination, and decided to distribute sweets to the students according to their test scores . He shall distribute sweets according to the following conditions :
i) Every student must get atleast one sweet.
ii) A student with higher score gets more number of sweets than all students who scored less than him.
Help Akash to find out the minimum number of sweets that need to be distributed. Since the answer can be very large output it modulo 10^{9} + 7.
Input
The input consists of 3 lines. The first line contains T (1<=T<=10) denoting the number of test cases. The second line consists of a single interger N (1 <= N <= 10^{5}) denoting the number of students.
The next line consists of N space separated integers a_{1,}a_{2,}a_{3...}a_{n} where a_{i }denotes the test score of the i^{th} student (0<=a_{i}<=10^{9}) .
Output
Output a single integer denoting the minimum number of sweets to be distributed by Akash.
Example
Input:
2 2 1 2 3 100 200 50
Output:
3 6
hide comments
vinay1998:
2019-08-25 17:44:01
Mind the mod (10^9)+7, cost me 1 WA. Pretty straight forward other than that. Last edit: 2019-08-25 17:44:51 |
Added by: | suraj1611 |
Date: | 2019-05-26 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |