$\quad$ Denote $m_k=\min_{1 \leq i \leq k} a_i; M_k=\max_{1 \leq j \leq k} a_j$. $\quad$ Property $P1$: If $m_k<a_{k+1}<M_k$, then $b_{k+1}=b_k=m_k+M_k$, hence, in this situation, the permutation isn't guadiana. $\quad$ Property $P2$: For $1\le k\le n-2$, if $a_{k+1}<m_k-1$ or $a_{k+1}>M_k+1$, the permutation isn't guadiana. Proof: If $a_{k+1}<m_k-1$, then $\exists p\in\mathbb{N}, k+2\le p\le n$ such that $a_p=m_k-1$. Results $m_{p-1}\le a_{k+1}<a_p<m_k\le M_{k}\le M_{p-1}$, hence $m_{p-1}<a_p<M_{p-1}$ and applying $P1$, results that the permutation isn't guadiana. Similar proof for $a_{k+1}>M_k$. Results: If a permutation is guadiana, then $a_{k+1}=m_k-1$ or $a_{k+1}=M_k+1$ $\quad$ Property $P3$: If $a_{k+1}=m_k-1$ or $a_{k+1}=M_k+1,\; \forall 1\le k\le n-1$, then the permutation is guadiana. Proof: If $a_{k+1}=m_k-1$, then $b_{k+1}=b_k-1$; If $a_{k+1}=M_k+1$, then $b_{k+1}=b_k+1$. Results $b_k\ne b_{k+1},\;\forall k\in\{1,2,\dots, n-1\}$, hence the permutation is guadiana. $\quad$ From $P2$ and $P3$ results: $\quad$ Property $P4$: A permutation is guadiana if and only if $a_{k+1}=m_k-1$ or $a_{k+1}=M_k+1,\; \forall k\in\{1,2,\dots, n-1\}$. $\quad$ Let $a_1=k\in\{1,2,\dots,n-1\}$. In the sequence $a_2, a_3,\dots,a_n$ exist $k-1$ therms of the permutation less than $k$ and using $P4$, these therms must appear in the order $k-1, k-2, \dots, 1$. Also, exist $n-k$ therms of the permutation greater than $k$ and using $P4$, these therms must appear in the order $k+1, k+2,\dots,n$. $\quad$ The $k-1$ therms less than $k$ can be placed in $C_{n-1}^{k-1}$ ways. For each configuration, the therms greater than $k$ can be placed in unique way. $\quad$ Results the total number of guadiana permutations: $\quad$ $N_g=\sum_{k=1}^{n}C_{n-1}^{k-1}=\sum_{p=0}^{n-1}C_{n-1}^{p}$. $\quad$ $N_g=2^{n-1}$.

Alternatively, write the numbers $1,2,\dots,n$ in a chalkboard. We cross out $a_1$ first, and on the $k-$th turn we cross out $a_k$; this must be either the least crossed out term minus one or the greatest crossed out number plus one, or else our permutation is not guardiana. Fixing $a_1$, permuting this is equivalent to permuting $a_1-1$ ones in a $n-1$ digit binary representation. Varying $a_1$ from $1$ to $n$ means we are counting all binary representations of $n-1$ digits, so our answer is $2^{n-1}$.

I proposed this problem. Here are the solutions I sent, which are probably somewhat similar to the ones already here. In all solutions we let $m_i$ and $M_i$ denote the minimum and maximum of $a_1, a_2, \dots, a_i$, respectively. First Solution We build all of these permutations by choosing $a_n, a_{n - 1}, \dots, a_1$ in that order. Assume that in some moment we are choosing the value of $a_k$, $k \geq 2$, and that the values $m_k = x_1 < x_2 < \dots < x_k = M_k$ are the ones that have not been assigned to an element of the permutation. If $a_k \neq x_1$ and $a_k \neq x_k$ then both $x_1$ and $x_k$ belong to the subsequence $a_1, a_2, \dots, a_{k - 1}$, implying that $m_{k - 1} = x_1 = m_k$ and $M_{k - 1} = x_k = M_k$, so $b_{k - 1}$ and $b_k$ are equal and the resulting permutation is not guadiana. Thus in each step there are only two choices that could possibly give us a guadiana permutation. There are $n - 1$ steps and each one has two possibilities, giving a total of $2^{n - 1}$ permutations. But it's easy to check that each one of these permutations is guadiana, so there are $2^{n - 1}$ in all. Second Solution This is essentially the same as the previous solution, but phrased in an inductive language. Let $f(n)$ be the number of guadiana permutations. Trivially $f(1) = 1$. For the inductive step, extend the definition of guadiana to apply to any sequence of real numbers. By the same argument as in the previous solution we have either $a_n = 1$ or $a_n = n$ in any guadiana permutation. If $a_n = n$ then $a_1, a_2, \dots, a_{n - 1}$ is a guadiana permutation of $1, 2, \dots, n - 1$, of which there are $f(n - 1)$. It is easy to verify that appending $n$ to this permutation mantains the guadiana condition, as $b_{n - 1} = n \neq n + 1 = b_n$. Similarly, if $a_n = 1$, then sequence $a_1, a_2, \dots, a_{n - 1}$ is a guadiana permutation of $\{2, 3, \dots, n\}$, so $a_1 - 1, a_2 - 1, \dots, a_n - 1$ is a guadiana permutation of $1, 2, \dots, n - 1$, of which there are $f(n - 1)$. After appending $1$ the resulting permutation is guadiana as $b_{n - 1} = n + 2 \neq n + 1 = b_n$. This shows that $f(n) = 2f(n - 1)$, and because $f(n - 1) = 2^{n - 2}$ by the inductive hypothesis we get $f(n) = 2^{n - 1}$. This completes the induction. Third Solution We biject guadiana permutations with $0-1$ sequences of length $n - 1$. By the same argument as in the first solution we must have either $a_k = M_k$ or $a_k = m_k$ for each $k \geq 2$. Thus we can assign to each guadiana permutation the $0-1$ sequence $x_1, x_2, \dots, x_{n - 1}$ where $x_i = 1$ if and only if $a_{i + 1} = M_{i + 1}$. We now reconstruct a guadiana permutation from its $0-1$ sequence. Assume that there are exactly $m$ zeroes in the sequence, so $a_k = m_k$ for $k \geq 2$ exactly $m$ times. Notice that if $a_k = m_k$ then $a_k < a_1$, so there exist at least $m$ values in the permutation that are less than $a_1$. Similarly there are at least $n - 1 - m$ values in the permutation that are greater than $1$. This clearly implies that $a_1 = m + 1$. Furthermore, the values less than $a_1$ must form a decreasing subsequence in the permutation, as $a_1 > a_i > a_j$ implies $m_j = a_j < a_i = m_i$, and because $(m_i)$ is clearly a decreasing sequence this implies $j > i$. Similarly the values greater than $a_1$ must form an increasing subsequence. Because their positions are given by the $0-1$ string we are given, this allows us to reconstruct the permutation uniquely. So the number of guadiana permutations is equal to the number of $0-1$ sequences of length $n - 1$, which is clearly $2^{n - 1}$.

I'm not sure why my solution is so simple, can someone check it? Consider choosing $a_i$ from $1$ to $n$. Evidently each time your minimum must be replaced or your maximum must be replaced when determining the next $b_i$. Clearly, they can't be replaced at the same time except when choosing the first number, and each number must be either a minimum or maximum at some point. Therefore say at some point our current set of $a_1, \dots a_i$ doesn't consist of a contiguous block of $1, 2, \dots, n$. Then that number in the range $\min(a_i), \max(a_i)$ that isn't one of the $a_i$ will never be a max or a min, contradiction. Thus, say we start with $i$. Then we can either choose on the lower side $i-1$ times or on the higher sie $n-i$ times. Thus there are $\binom {n-1}{i-1}$ ways to do this, and summing and using binomial theorem yields $2^{n-1}$ ways.

A very simple solution: Let $f(n)$ denote the number of such permutations for a given $n$. If both $1$ and $n$ are in the numbers $a_1,a_2,\cdots a_{n-1}$, then $b_{n-1}=b_n=n+1$, impossible, so we get that $a_n$ is either $1$ or $n$. Now for $a_1,a_2,\cdots a_{n-1}$ we get $f(n-1)$ such permutations in either case$\Rightarrow $ We get that $f(n)=2f(n-1)$, but we easily find that $f(2)=2$, thus $f(n)=2^{n-1}$.$ \blacksquare $

Claim: $b_{k+1}-b_k=1$ Assume the contrary, clearly $b_{k+1}-b_k \not = 0$ by assumption. So, $b_{k+1}-b_k \geq 2$. Thus, there exists an unslected $i$ which will not be the maximum or minimum. Taking $a_j=i$ we see $b_j=b_{j-1}$. Contradiction. Notice that each new $a_i$ must be directly adjacent to the previous $a_i$'s and can either be the left side or the right side. For any $a_1=r$ we define a $n-1$ digit long binary sequence for which the $m$th digit is 1 if $a_m$ is placed to the left and 0 if placed to the right. Clearly, the only restriction on our binary sequence is that it must have exactly $r-1$ 1's. Thus, as $r$ ranges from $1$ to $n$, we cover all possible binary sequences exactly once. Yielding $2^{n-1}$