First, observe that there are two possibilities for the long term behaviour of the elves:

1. All the houses have ~\ge 1~ elf in them and the number of elves in each house stays constant.
2. All the houses have exactly ~0~ or ~1~ elves and each elf continues cycling around the houses forever.

The first case is eventually reached iff ~\sum_{i=1}^N a_i \ge N~ and the second case is reached otherwise. It can be shown that it takes at most ~N~ iterations to reach one of the cases. If ~K \le N~ we can calculate the number of elves at each house after ~K~ hours directly. Otherwise, we will calculate the number of elves at each house after ~N~ hours. In the first case, this will be the same as after ~K~ hours. In the second, we will need to rotate the result by ~K \bmod N~ to get the number of elves in each house after ~K~ hours.

Let ~M = \min(N, K)~. We are interested in the number of elves at each house after ~M~ hours. To calculate this, we will iterate over all houses, ~i~ ~(1 \le i \le N)~, and maintain a data structure that stores for each ~j~ ~(1 \le j \le M)~ whether there was an elf arriving at house ~i~ at time ~j~. A simple but inefficient way of implementing such a data structure would be to have a boolean array, ~ds~, of length ~M~ where ~ds[j] = 1~ corresponds to an elf arriving at time ~j~. We initialize this data structure with values corresponding to house ~1~, which can be found relatively easily by iterating through the original array backwards. To update this data structure when moving from house ~i~ to house ~i+1~, we shift every value in ~ds~ to the right by ~1~ and replace the first ~a_i~ 0s with 1s. The number of elves at the current house ~i~ at time ~M~ can be calculated by ~\max(ds[M], a_i - \sum_{j=1}^M !ds[j])~. This already yields an ~\mathcal{O}(N^2)~ solution.

We can optimize this by replacing the boolean array with a stack of integers where each value corresponds to the index of a ~0~ value in our old ~ds~ array. More specifically, if we are currently at house ~i~, a value ~v~ in the stack represents that there will be no elves arriving at house ~i~ at time ~v+i~. This representation allows us to avoid having to shift every value by ~1~ when transitioning between houses. To find the number of elves at each house at time ~M~, we use the same strategy as we did with the boolean array, except now we binary search on our stack to find the number of time points in which no elf arrived at house ~i~. This binary search can be replaced with a pointer that always points to the smallest element smaller than ~M-i~ and gets updated at every transition, which removes a log factor from the complexity.

Time Complexity: ~\mathcal{O}(N)~ or ~\mathcal{O}(N \log N)~