# ZigZagEscape (Chromium 2017 Challenge)

This page displays a solution to Codility’s Chromium 2017 Challenge. The problem’s given name is ZigZagEscape.

The following solution attains 90% score under Codility’s test, it is therefore NOT a golden award solution.

```
def solution(H):
N = len(H)
stack = []
array1 = *N
stack.append((0, H))
array1 = (0, 1000000010)
for idx, elem in enumerate(H):
while stack[-1] < elem:
stack.pop()
if stack == []:
stack.append((idx, elem))
array1[idx] = (idx, 1000000010)
break
if stack[-1] > elem:
array1[idx] = stack[-1]
stack.append((idx, elem))
stack = [(N-1, H[-1])]
for idx, elem in enumerate(reversed(H)):
while stack[-1] < elem:
stack.pop()
if stack == []:
stack.append((N-idx-1, elem))
break
if stack[-1] > elem:
if array1[N-idx-1] > stack[-1]:
array1[N-idx-1] = stack[-1]
stack.append((N-idx-1, elem))
array2 = []
for x in xrange(N):
array2.append(((H[x], x), array1[x]))
array2.sort(reverse = True)
POS = *N
for k in xrange(N):
POS[k] = (array2[k], k)
POS.sort()
F = []
for i in xrange(N):
F.append((array2[i], POS[array2[i]]))
dp = [((0,0), 0)]
total = N
for i in xrange(1, N):
sum_l = dp[F[i]]
sum_r = dp[F[i]]
current = F[i]
for j in xrange(dp[F[i]], i):
if F[j] < current:
sum_l += sum_r +1
else:
sum_r += sum_l +1
dp.append(((sum_l, sum_r), i))
total += sum_l + sum_r
total %= 1000000007