from collections import deque
 
def diff_sliding_window(arr, win):
 
    if win > len(arr):
        return []
 
    win_maxes = [] # max of each window
 
    #Q contains indexes of items in the window that are greater than
	#all items to the right of them.  This always includes the last item
	#in the window
    Q = deque()
 
    #fill Q for initial window
    for i in range(win):
        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
    win_maxes.append(arr[Q[0]])
 
    for i in range(win, len(arr)):
        #remove indexes (at most 1, really) left of window
        while len(Q) > 0 and Q[0] <= (i-win):
            Q.popleft()
 
        #remove anything that isn't greater than the new item
        while len(Q) > 0 and arr[i] >= arr[Q[-1]]:
            Q.pop()
        Q.append(i)
        win_maxes.append(arr[Q[0]])
 
    return win_maxes
 
print(diff_sliding_window([12, 1, 78, 90, 57, 89, 56],3))
print(diff_sliding_window([1, 3, -1, -3, 5, 3, 6, 7],3))
 

ZnJvbSBjb2xsZWN0aW9ucyBpbXBvcnQgZGVxdWUKCmRlZiBkaWZmX3NsaWRpbmdfd2luZG93KGFyciwgd2luKToKIAogICAgaWYgd2luID4gbGVuKGFycik6CiAgICAgICAgcmV0dXJuIFtdCiAgICAgICAgCiAgICB3aW5fbWF4ZXMgPSBbXSAjIG1heCBvZiBlYWNoIHdpbmRvdwogICAgCiAgICAjUSBjb250YWlucyBpbmRleGVzIG9mIGl0ZW1zIGluIHRoZSB3aW5kb3cgdGhhdCBhcmUgZ3JlYXRlciB0aGFuCgkjYWxsIGl0ZW1zIHRvIHRoZSByaWdodCBvZiB0aGVtLiAgVGhpcyBhbHdheXMgaW5jbHVkZXMgdGhlIGxhc3QgaXRlbQoJI2luIHRoZSB3aW5kb3cKICAgIFEgPSBkZXF1ZSgpCgogICAgI2ZpbGwgUSBmb3IgaW5pdGlhbCB3aW5kb3cKICAgIGZvciBpIGluIHJhbmdlKHdpbik6CiAgICAgICAgI3JlbW92ZSBhbnl0aGluZyB0aGF0IGlzbid0IGdyZWF0ZXIgdGhhbiB0aGUgbmV3IGl0ZW0KICAgICAgICB3aGlsZSBsZW4oUSkgPiAwIGFuZCBhcnJbaV0gPj0gYXJyW1FbLTFdXToKICAgICAgICAgICAgUS5wb3AoKQogICAgICAgIFEuYXBwZW5kKGkpCiAgICB3aW5fbWF4ZXMuYXBwZW5kKGFycltRWzBdXSkKICAgIAogICAgZm9yIGkgaW4gcmFuZ2Uod2luLCBsZW4oYXJyKSk6CiAgICAgICAgI3JlbW92ZSBpbmRleGVzIChhdCBtb3N0IDEsIHJlYWxseSkgbGVmdCBvZiB3aW5kb3cKICAgICAgICB3aGlsZSBsZW4oUSkgPiAwIGFuZCBRWzBdIDw9IChpLXdpbik6CiAgICAgICAgICAgIFEucG9wbGVmdCgpCiAgICAgICAgICAgIAogICAgICAgICNyZW1vdmUgYW55dGhpbmcgdGhhdCBpc24ndCBncmVhdGVyIHRoYW4gdGhlIG5ldyBpdGVtCiAgICAgICAgd2hpbGUgbGVuKFEpID4gMCBhbmQgYXJyW2ldID49IGFycltRWy0xXV06CiAgICAgICAgICAgIFEucG9wKCkKICAgICAgICBRLmFwcGVuZChpKQogICAgICAgIHdpbl9tYXhlcy5hcHBlbmQoYXJyW1FbMF1dKQogICAgCiAgICByZXR1cm4gd2luX21heGVzCgpwcmludChkaWZmX3NsaWRpbmdfd2luZG93KFsxMiwgMSwgNzgsIDkwLCA1NywgODksIDU2XSwzKSkKcHJpbnQoZGlmZl9zbGlkaW5nX3dpbmRvdyhbMSwgMywgLTEsIC0zLCA1LCAzLCA2LCA3XSwzKSkK