\nSachin is teaching a group of N students. Now every student has an arrogance level. He make all the N students lined up in a row. Now what he saw was a student was forcefully handing over his assignments to the person closest and in front of him with a lower arrogance level. So if the ith students hands over his assignments to the jth student then Sachin reducts j\u2212i+1 marks from the class discipline.
\nFind the number of marks deducted after some students hand over their assignments to others.<\/p>\n<\/blockquote>\n
<\/strong><\/u><\/a><\/p>\nTest Case:<\/h4>\nInput:\n1\n5\n1 2 3 2 1\n\nOutput:\n7\n\nExplanation:\nStudent standing at index 0 is the smallest and hence does not have any other student with less arrogance number than him. So, he cannot give his assignment to anybody;\nStudent at index 1 gives his assignment to the student at index 4 as its arrogance number is less than his. So,his contibution in deducted marks is (4-1+1)=4;\nStudent at index 2 gives his assignment to the one at index 3,hence his contribution becomes (3-2+1)=2;\nSimilarly,student at index 3 contributs (4-3+1)=2.<\/code><\/pre>\nSolving Approach :<\/h4>\n
Starting from the last index we pop elements from stack until we encounter an element lesser than it. In the process, if stack becomes empty that means the student at that particular index does not give his assignment to any other student.We keep pushing elements to the stack.<\/p>\n
Solutions:<\/h3>\n\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645095974440-Article_261.png\")
<\/p>\n