Vasily has a deck of cards consisting of n cards. There is an integer on each of the cards, this integer is between 1 and 100 000, inclusive. It is possible that some cards have the same integers on them.

Vasily decided to sort the cards. To do this, he repeatedly takes the top card from the deck, and if the number on it equals the minimum number written on the cards in the deck, then he places the card away. Otherwise, he puts it under the deck and takes the next card from the top, and so on. The process ends as soon as there are no cards in the deck. You can assume that Vasily always knows the minimum number written on some card in the remaining deck, but doesn't know where this card (or these cards) is.

You are to determine the total number of times Vasily takes the top card from the deck.

Input

The first line contains single integer n (1 ≤ n ≤ 100 000) — the number of cards in the deck.

The second line contains a sequence of n integers a1, a2, ..., an (1 ≤ ai ≤ 100 000), where ai is the number written on the i-th from top card in the deck.

Output

Print the total number of times Vasily takes the top card from the deck.

Examples

Input

4
6 3 1 2


Output

7


Input

1
1000


Output

1


Input

7
3 3 3 3 3 3 3


Output

7

Note

In the first example Vasily at first looks at the card with number 6 on it, puts it under the deck, then on the card with number 3, puts it under the deck, and then on the card with number 1. He places away the card with 1, because the number written on it is the minimum among the remaining cards. After that the cards from top to bottom are [2, 6, 3]. Then Vasily looks at the top card with number 2 and puts it away. After that the cards from top to bottom are [6, 3]. Then Vasily looks at card 6, puts it under the deck, then at card 3 and puts it away. Then there is only one card with number 6 on it, and Vasily looks at it and puts it away. Thus, in total Vasily looks at 7 cards.
import static java.util.Arrays.sort;
import static java.util.Collections.*;

import java.util.*;

public class B {

	public B () {
		int N = sc.nextInt();
		int [] A = sc.nextInts();

		int [] J = si(A); int S = -1, p = 0, j = 0, v = A[J[0]];
		Fenwick H = new Fenwick(N);
		long res = 0;

		for (@SuppressWarnings("unused") int n : rep(N)) {
			int T = J[j];
			res += (T - S) - (H.get(T+1) - H.get(S+1));
			if (T < S)
				res += N - H.get(N);
			J[j++] = -1;
			H.add(1, S = T);
			if (j == N || (J[j] >= 0 && A[J[j]] > v))
				j = p;
			if (J[j] == -1) {
				while (p < N && J[p] == -1) ++p;
				if (p < N) {
					v = A[J[j = p]];
					while (j < N && A[J[j]] == v && J[j] < S) ++j;
					if (j == N || A[J[j]] > v)
						j = p;
				}
			}
		}

		exit(res);
	}

	private static Integer [] obj (int ... A) { Integer [] res = new Integer [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static int [] pri(Integer [] A) { int [] res = new int [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static <T extends Comparable<T>> int [] si(int [] A) { return si(obj(A)); }
	private static <T extends Comparable<T>> int [] si(final T [] X) { return si(X, reverseOrder(reverseOrder())); }
	private static <T> int [] si(final T [] X, final Comparator<T> C) {
		int N = X.length;
		Integer [] res = obj(rep(N));
		sort(res, new Comparator<Integer>() {
			public int compare(Integer i, Integer j) {
				int res = C.compare(X[i], X[j]);
				return res != 0 ? res : i.compareTo(j);
			}
		});
		return pri(res);
	}
	private static class Fenwick {
		private final long [] X;
		private final long MOD;
		public Fenwick(int N) { X = new long [N]; MOD = 0; }
		public void add(long x, int i) {
			++i; assert i <= X.length;
			while (i <= X.length) {
				X[i-1] += x;
				if (MOD > 0) X[i-1] = ((X[i-1] % MOD) + MOD) % MOD;
				i += (i & (-i));
			}
		}
		public long get(int to) {
			assert to <= X.length;
			long res = 0;
			for (; to > 0; to -= (to & (-to))) {
				res += X[to-1];
				if (MOD > 0) res = ((res % MOD) + MOD) % MOD;
			}
			return res;
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	private final static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static void exit (Object o, Object ... A) { IOUtils.print(o, A); IOUtils.exit(); }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public int nextInt() { return Integer.parseInt(next()); }
			public String nextLine() { line = null; return readLine(); }
			public String [] nextStrings() { return split(nextLine()); }
			public int [] nextInts() {
				String [] L = nextStrings();
				int [] res = new int [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Integer.parseInt(L[i]);
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static void start() { if (t == 0) t = millis(); }
		private static void append(StringBuilder b, Object o, String delim) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					append(b, java.lang.reflect.Array.get(o, i), delim);
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					append(b, p, delim);
			else {
				if (o instanceof Double)
					o = new java.text.DecimalFormat("#.############").format(o);
				b.append(delim).append(o);
			}
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print(Object o, Object ... A) { pw.println(build(o, A)); }
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(IOUtils.time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
	}
	public static void main (String[] args) { new B(); IOUtils.exit(); }
}
