One day, a little girl named Tasfi was sitting in the park. Suddenly, she saw a bag lying on the park having some important documents in it. So, she wanted to return this bag to the parson who left it in the park. She saw in the bag that there was a number sequence and the sequence contained n positive numbers. The address of that person who left this bag can be found from this sequence of numbers. The longest strictly decreasing consecutive sub-sequence of this number sequence contains the house number and the road number of that person. The total sum of the longest strictly decreasing consecutive sub-sequence will be the house number of that person and the second lowest number of longest strictly decreasing consecutive sub-sequence will be the road number of that person. If there are multiple sequence having the longest length, then the very last sequence among those will be the desired one.
Tasfi was able to solve this problem. But now, it’s your turn to solve it. It’s ensured that there will always exist some decreasing sequence in the n elements.
Input
The first line contains an integer n (2 ≤ n ≤ 10^5) — the number of elements in the bag. The second line contains n integers a1, a2, ... an (1 ≤ ai ≤ 10^5) — the elements of the bag.
Output
Print “House No” before printing the house number and print “Road No” before printing the road number. For better understand see the sample output. Answer the house number modulo 10000007.
Samples
| Input | Output |
|---|---|
7 1 1 5 3 2 8 3 | House No = 10 Road No = 3 |
| Input | Output |
|---|---|
10 1 2 3 10 4 3 6 4 3 1 | House No = 14 Road No = 3 |
| Input | Output |
|---|---|
5 1 3 2 5 6 | House No = 5 Road No = 3 |
Explanation: For sample test case 2, the last longest strictly decreasing consecutive sub-sequence is 6 4 3 1. The House Number is = 6 + 4 + 3 + 1 = 14 and the Road Number is = 3.
