### PROBLEM LINK:

**Author:** Hasan Jaddouh

**Testers:** Kamil Debowski

**Editorialist:** Hasan Jaddouh

# Difficulty:

Easy-medium

# Pre-requisites:

combinatorics

# Problem Statement:

Given an array A of length N, some of its elements are missing and they are replaced with -1, you are required to count number of ways to fill missing elements such that A_{i} = A_{i-1} + 1 or A_{i} = 1, and A_{1} = 1

# Explanation

We know that if some number A_{i} is greater than 1, a previous number (at index i-1) must be equal to A_{i} - 1. If this number is also greater than 1, a number at index i-2 must be A_{i} - 2, and so on.

If we encounter inconsistency during this process (for example A_{i} = 17 and A_{i-1} = 10), there are 0 ways (we can print 0 and proceed to the next test case).

in addition we can determine that first element is equal to 1.

now after we determined the values of all elements that can be determined we count the number of elements that can’t be determined and let’s say their number is **K** then the answer is simply 2^{K} that’s because every element of them can have two possibilities, either it is equal to previous element+1 or it’s equal to 1

# determining the value of all elements that can be determined in O(N)

We iterate over the array from the end to the beginning when we are at index i, if A_{i+1} is known and is bigger than 1 then we can know the value of A_{i} so if A_{i} is equal to -1 we just set its new value, otherwise if it’s known from the input we should make sure that it’s consistent

the last thing is to make sure A_{1} = 1, after that we count the number of elements that are still not determined - let it be **K** - then output 2^{K}

time complexity: O(N)