# PROBLEM LINK:

# DIFFICULTY:

Easy

# PREREQUISITES:

Combinatorics, Fast Expontiation

# PROBLEM:

Given an integer **N**, count the number of permutations that is increasing up to a certain point then deceasing after that.

# EXPLANATION:

## finding the formula

considering that this problem is requiring us to count something and that the constraints on N is very high this will hint us that the solution will be probably using combinatorics

let’s say that we have an empty array of length **N** and we want to put the numbers from 1 to **N** in this array and satisfy the problem requirements, now let’s say we want to add the number 1, we have **N** ways to put this number on the array but if we notice that we should not make 3 consecutive numbers such that the one in the middle is the minimum number among these 3 numbers then we will know that we cannot put the number 1 on any cell except the first and the last cells, because otherwise the number 1 will be in the middle of two bigger number eventually. So in conclusion we have only 2 possible ways to put the number 1, since we have put it in a border cell then we can imagine that we have an array of length **N-1** and now we want to put the number 2, again for the same reasons we have two ways and so on, until we want to put the number **N** we will only have 1 way instead of 2, so we have **N-1** number that have 2 ways to put, so by multiplication rule of combinatorics the answer is **2 ^{N-1}**, finally we should subtract 2 from the answer because permutations 1 2 3 4 …

**N**and

**N**

**N-1**… 3 2 1 should not be counted. we also should treat the case

**N=1**alone because those two permutations become the same so we should subtract 1 instead of 2

to sum up, the answer is **2 ^{N-1}-2** for all

**N**>1 and 0 for

**N**=1

## algorithm for calculating the formula

an O(n) algorithm for calculating the formula would get the score of only the first sub-task so we need a faster way to compute it, fortunately there’s O(log n) algorithm for it which is called “Exponentiation by squaring”, you can find details about it here “https://en.wikipedia.org/wiki/Exponentiation_by_squaring”

the algorithm works by observing that **2 ^{N} = 2^{N/2} * 2^{N/2}** if

**N**is even, in this case we only need to recursively calculate

**2**once then squaring it. if

^{N/2}**N**is odd it’s very similar, we have

**2**so we only need to recursively calculate

^{N}= 2^{(N-1)/2}* 2^{(N-1)/2}* N**2**then square it then multiply it by

^{(N-1)/2}**N**

since we always divide **N** by 2 then this algorithm takes only **O(log N)** steps

pseudo code:

```
power2(int N){
if(N==0){
return 1
} else if(N is even){
int H=power2(N/2)
return H*H
} else {
int H=power2((N-1)/2)
return H*H*2
}
}
```

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.