What is the total number of ways in which we can choose pairs of $a_i$ and $a_j$ between a sequence of increasing sorted numbers numbers $a_1,a_2,a_3,\ldots,a_n$ such that $a_1\le a_i\le a_j\le a_n$.
[Math] the number of distinct combinations for choosing a pair of numbers between a sorted sequence
combinatorics
Related Solutions
Partial solution.
Claim: When $n$ is of the form $n = 2^k-1$, then $m=n+1 = 2^k$ suffices, i.e. such $m$ is an upperbound on the OP's required minimum.
Corollary: For any $n$, taking $m = 2^k > n$ for the smallest such power-of-$2$ suffices.
Fine-print: as @mathworker21 pointed out, in both claims above, I am including only non-trivial events, i.e. those with prob strictly $\in (0,1)$. We can always include two more events $\emptyset$ and $\Omega$ since with $P(\emptyset)=0, P(\Omega)=1$, each is independent of any event.
Consider flipping $k$ independent fair coins, which can obviously be simulated by rolling an $m=2^k$ sided die. Let $S$ be a non-empty subset of ($1$ to $k$) coin(s), and let $N(S)=$ the number of Heads among coins in $S$, modulo $2$. Note that there are $2^k-1$ distinct non-empty subsets of coins, and therefore $2^k-1$ distinct events of the form $N(S)=0$. The main claim now follows from:
Lemma: If $S,T$ are two different non-empty subsets, then event $N(S)=0$ and event $N(T)=0$ are pairwise independent.
Proof: Clearly $P(N(S)=0) = P(N(T)=0) = 1/2$. OTOH:
Event $(N(S)=0 \cap N(T)=0) =$ event $(N(S-T) = N(S\cap T) = N(T-S))$
The subsets $S-T, S \cap T, T-S$ are disjoint.
Since $S,T$ are different and non-empty, either $2$ or all $3$ of the subsets $S-T, S\cap T, T-S$ are non-empty.
If $1$ of them is empty, the other two must both have an even number of Heads, i.e. prob $1/4$.
If all of them are non-empty, all three must have the same parity of number of Heads, i.e. prob $2 \times 1/8 = 1/4. ~~~~~\square$
Roughly, $\min(|A|+|B|)=2\sqrt n$.
Given two lists $A$ and $B$ satisfying your constraints, it must be true that $$ |A|\cdot |B|\ge n $$ because the given restrictions imply that the ordered pairs $$ (a_1,b_1),(a_2,b_2),\dots,(a_n,b_n) $$ are all distinct. Indeed, if $(a_i,b_i)=(a_j,b_j)$, that would contradict the condition $a_i=a_j\implies b_i\neq b_j$. Since there are at most $|A|\cdot |B|$ distinct ordered pairs, the size of the above list is at most $|A|\cdot |B|$.
The fact that $|A|\cdot |B|\ge n$ readily implies that $|A|+|B|\ge 2\sqrt n$:
$$
|A|+|B|\ge |A|+\frac{n}{|A|}=2\sqrt n+\left(\sqrt{A}-\sqrt{n\over |A|}\right)^2\ge 2\sqrt n
$$
To see that this bound is achievable, given $n$, let $m=\lceil \sqrt n\rceil$, and define
$$
a_i=\lfloor i/m\rfloor ,\\
b_i= i\;\text{ rem }\;m
$$
for each $i\in \{1,\dots,n\}$. Here, $i\;\text{ rem }\;m$ means the remainder when $i$ is divided by $m$, and is the unique element of $\{0,1,\dots,m-1\}$ which is congruent to $i$ modulo $m$. (This is the % operator in many programming languages).
Since the ordered pairs $(a_i,b_i)$ are all distinct (which is a consequence of how integer division works), this satisfies your constraints. Furthermore, there are only $n/m\le m$ distinct values for $A$ and $m$ distinct values for $B$, so $|A|+|B|\le 2m\approx 2\sqrt n$.
Best Answer
In fact, any pair of elements you choose will always fulfill the condition (as there will always be one greater than the other one, and both between the smallest and the greatest, including these two!), thus you have to calculate the number of sets with two elements out of a set with $\,n\,$ elements, i.e. $$\binom{n}{2}=\frac{n!}{2!(n-2)!}=\frac{(n-1)n}{2}$$ ADDED: as Binn points out in the comment below, the condition $\,a_1\leq a_i\leq a_j\leq a_n\,$ implies that we can choose the same element twice, even if the wording "...choose pairs.." can be misleading.
This being the case, we must add $\,n\,$ cases to the above number, each for every element chosen twice, and we thus get the number $$\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}$$