# PROBLEM LINKS :

**Author** and **Editorialist** Vineet Paliwal

**Tester** Roman Rubanenko

# DIFFICULTY :

## Cakewalk

# PREREQUISITES :

## Stacks , Queue , Modulo , Modular Arithmetic , Modular Multiplication

# PROBLEM :

Given N chefs in a queue , each chef may delegate his/her task to the junior least ahead of him and go away . The Head Chefs fearfulness of the scenario is the difference in index of the two positions + 1 . Head Chef’s total fearfulness is product of individual fearfulness corresponding to each chef . Find total fearfulness . In case no junior lies ahead the fearfulness is 1 .

# EXPLANATION:

### The Naive Solution :

For each chef look at all chefs ahead of this chef in the queue till you find a junior chef and then update the Head Chef’s fearfulness . This has a time complexity of O(N^2) .

### Using Stacks :

Start with given queue and an empty stack(of a structure of numbers and their indexes) .

For each chef put him on a stack if the top of stack is not senior to him otherwise pop out as many senior chefs from the stack as possible ( updating Head Chef’s fearfulness at each pop ) and finally push the chef on the stack .

The time complexity of this solution is O(N) .

### Example Using Stacks :

Given the queue , 8 3 7 8 9 12 13 11 3 4

Initialize ans = 1 ; sp = 1000000007

Step One : Stack == [8,1]

Step Two : Stack == [3,2] ( ans *= ( 2 - 1 + 1 ) , ans %= sp => ans = 2 )

Step Three : Stack == [3,2] [7,3] ( ans remains same )

Step Four : Stack == [3,2] [7,3] [8,4] ( ans remains same )

Step Five : Stack == [3,2] [7,3] [8,4] [9,5] ( ans remains same )

Step Six : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] ( ans remains same )

Step Seven : Stack == [3,2] [7,3] [8,4] [9,5] [12,6] [13,7] ( ans remains same )

Step Seven : Stack = [3,2] [7,3] [8,4] [9,5] [11,8] ( Two elements are popped out , ans need to be multiplied by 2 and 3 corresponding to each of pop . So ans = 12 )

Step Eight : Stack == [3,2] [3,9] ( Four elements are popped out . ans need to be multiplied (modularly) by 2 , 5 , 6 , 7 )

Step Nine : Stack == [3,2] [3,9] [4,10] .

Finish and output ans .

### Point to Remember :

Take modulus with the special number given after each multiplication .