Problem M
Who Ruined the Show?
After the concert is over, all of the upset audience members meet up with the goal of finding the one person who made the most people upset (they want to send them a strongly worded letter about what they believe is good crowd etiquette). Luckily, because all of the upset audience members are observant, they were able to approximate the height of everyone in their respective line of crowd members, but they don’t know how to actually figure out who made the most people upset.
One of the upset crowd members suggests coming to you, saying that you are the best problem solver in town. So, they all come to you and present to you every line of crowd members one at a time. Each line they show you is ordered from left to right (left being the front and right being the back), and at each position they give you the height of the crowd member. Once you have seen every line, all you need to do is tell them which person made the most people upset.
A person is upset if there is a person in front of them who is taller than them (if they are the same height, they can just lean their head around theirs). A person makes people upset if they are the first person taller than them in their line of crowd members (this means only one person can make a person upset, even if there is another person further ahead who is taller).
Input
The first line of input contains two integers $n$ and $m$ ($1 \le n \le 100, 1 \le m \le 20\, 000$), where $n$ indicates the number of crowd lines you will receive, and $m$ indicates the number of people in each line.
Then follow $n$ lines, each containing $m$ integer numbers, where each number represents a person’s height in micrometers ($508\, 000 \le \text{height} \le 3\, 023\, 000$).
Output
Output the position of the single person who made the most people upset followed by the number of people they made upset. The position of a person is given as a pair of integer numbers comprising of the line they are in and their position in that line. Both values start at $1$, so the position of the first (left-most) person in the first line would be labeled $1\, \, 1$.
If there is a tie, always pick the later occurrence (the person seen later in the input).
| Sample Input 1 | Sample Output 1 |
|---|---|
3 5 1828800 1778000 1828800 1473200 1524000 1651000 1701800 1701800 1752600 1600200 1803400 1854200 1727200 1752600 1854200 |
3 2 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 1 1549400 1574800 1600200 |
3 1 0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4 8 1651000 1778000 1727200 1905000 1828800 1879600 2032000 1981200 1524000 1574800 1549400 1625600 1600200 1701800 1676400 1752600 1828800 1803400 1879600 1854200 1930400 1905000 1981200 1955800 1397000 1473200 1447800 1498600 1549400 1524000 1574800 1625600 |
1 4 2 |
