The nearest taller cow
Time Limit: 3000 ms
Memory Limit: 65536 KiB
Problem Description
Farmer Zhao's N cows (1 ≤ N ≤ 1,000,000) are lined up in a row. So each cow can see the nearest cow which is taller than it. You task is simple, given the height (0 < height ≤ 109) of each cow lined up in the row, to calculate the distance between each cow and its nearest taller cow, if it is the tallest cow in the row, such distance is regarded as n. You should output the average distance.
Input
For each test case:
Line 1: One integers, N
Lines 2: N integers. The ith integer is the height of the ith cow in the row.
Line 1: One integers, N
Lines 2: N integers. The ith integer is the height of the ith cow in the row.
Output
The average distance to their nearest taller cow, rounded up to 2 decimals.
Sample Input
7 7 6 5 8 6 4 10
Sample Output
2.43
Hint
Source
2009湖南大学校赛