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 java.util.*;
import java.io.*;
public class CardsSorting {
    
    
    
    /************************ SOLUTION STARTS HERE ************************/
    

    static class SplayTree /** The following implementation does not allow duplicates **/{
        private Vertex root;
        int arr[];
        public SplayTree(int arr[]) {
            this.arr = arr;
            root = build(0, arr.length - 1);
        }
        
        Vertex build(int L , int R) {
            if(L <= R) {
                int mid = (L + R) >> 1;
                Vertex v = new Vertex(arr[mid], null, null, null);
                v.left = build(L, mid - 1);
                v.right = build(mid + 1, R);
                update(v);
                return v;
            }
            
            return null;
        }
        
        long simulate() {
            long steps = 0;
            // System.out.println(this);
            for(int i = 1; i <= arr.length; i++) {
                // System.out.println("minPos = " + root.minPos);
                steps += root.minPos + 1;
                VertexPair pair = split(root, root.minPos);
                pair.left = pair.left.left; // remove min
                if(pair.left != null)
                    pair.left.parent = null;
                update(pair.left);
                root = merge(pair.right , pair.left);
                // System.out.println(this);
            }
            
            return steps;
        }
        
        static class Vertex {
            int key;
            // Sum of all the keys in the subtree - remember to update
            // it after each operation that changes the tree.
            int size;
            int minPos;
            int min;
            Vertex left;
            Vertex right;
            Vertex parent;

            Vertex(int key, Vertex left, Vertex right, Vertex parent) {
                this.key = this.min = key;
                this.size = 1;
                this.minPos = 0;
                this.left = left;
                this.right = right;
                this.parent = parent;
            }

            @Override
            public String toString() {
                return "[key = " + key + "]" + " p = " + (parent != null ? parent.key : "null") + " l = "
                        + (left != null ? left.key : "null") + " r = " + (right != null ? right.key : "null");
            }
        }

        static class VertexPair {
            Vertex left;
            Vertex right;

            VertexPair() {
            }

            VertexPair(Vertex left, Vertex right) {
                this.left = left;
                this.right = right;
            }
        }
        int size(Vertex v) {
            return v == null ? 0 : v.size;
        }
        private void update(Vertex v) {
            if (v == null)
                return;
            v.size = 1;
            v.min = Integer.MAX_VALUE;
            if (v.left != null) {
                v.left.parent = v;
                v.size += v.left.size;
                if(v.left.min < v.min) {
                    v.min = v.left.min;
                    v.minPos = v.left.minPos;
                }
            }
            
            if(v.key < v.min) {
                v.min = v.key;
                v.minPos = size(v.left);
            }
            
            if (v.right != null) {
                v.right.parent = v;
                v.size += v.right.size;
                if(v.right.min < v.min) {
                    v.min = v.right.min;
                    v.minPos = size(v.left) + 1 + v.right.minPos;
                }
            }
        }

        private void smallRotation(Vertex v) {
            Vertex parent = v.parent;
            if (parent == null) {
                return;
            }
            Vertex grandparent = v.parent.parent;
            if (parent.left == v) {
                Vertex m = v.right;
                v.right = parent;
                parent.left = m;
            } else {
                Vertex m = v.left;
                v.left = parent;
                parent.right = m;
            }

            update(parent);
            update(v);
            v.parent = grandparent;
            if (grandparent != null) {
                if (grandparent.left == parent) {
                    grandparent.left = v;
                } else {
                    grandparent.right = v;
                }
            }
            update(grandparent);

        }

        private void bigRotation(Vertex v) {
            if (v.parent.left == v && v.parent.parent.left == v.parent) {
                // Zig-zig left
                /*       a
                 *      /
                 *     /
                 *    b  
                 */
                smallRotation(v.parent);
                smallRotation(v);
            } else if (v.parent.right == v && v.parent.parent.right == v.parent) {
                // Zig-zig right
                /*
                 *  a
                 *   \
                 *    \
                 *     b
                 */
                smallRotation(v.parent);
                smallRotation(v);
            } else {
                /* Zig-zag
                 *    a    a
                 *    /    \
                 *    \    /
                 *     b   b
                 */
                smallRotation(v);
                smallRotation(v);
            }
        }

        private Vertex splay(Vertex v) {
            if (v == null)
                return null;
            while (v.parent != null) {
                if (v.parent.parent != null)
                    bigRotation(v);
                else
                    smallRotation(v);
            }
            return v;
        }

        
        VertexPair split(Vertex root, int pos) {
            VertexPair result = new VertexPair();
            Vertex piv = get(pos, root);
            result.left = splay(piv);
            if (result.left == null) {
                result.right = root;
                return result;
            }
            result.right = result.left.right;
            result.left.right = null;
            if (result.right != null)
                result.right.parent = null;
            update(result.left);
            update(result.right);
            return result;
        }

        Vertex get(int i, Vertex root) { // zero based index
            if (root != null) {
                if (i == size(root.left))
                    return root;
                else if (i < size(root.left))
                    return get(i, root.left);
                else
                    return get(i - size(root.left) - 1, root.right);
            } else
                return null;
        }

        Vertex merge(Vertex left, Vertex right) {
            if (left == null)
                return right;
            if (right == null)
                return left;
            right = splay(get(0, right));
            left = splay(get(left.size - 1, left));
            left.right = right;
            update(left);
            return left;
        }

        
        private StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb, Vertex root) {

            if (root == null) {
                sb.append("Tree Empty");
                return sb;
            }

            if (root.right != null) {
                toString(new StringBuilder().append(prefix).append(isTail ? "│   " : "    "), false, sb, root.right);
            }
            sb.append(prefix).append(isTail ? "└── " : "┌── ").append(root.key).append("\n");
            if (root.left != null) {
                toString(new StringBuilder().append(prefix).append(isTail ? "    " : "│   "), true, sb, root.left);
            }
            return sb;
        }

        @Override
        public String toString() {
            return this.toString(new StringBuilder(), true, new StringBuilder(), root).toString();
        }
    }

    
    private static void solve() {
        
        
        println(new SplayTree(nextIntArray(nextInt())).simulate());
        
        
    }
    
    
    
    /************************ SOLUTION ENDS HERE ************************/
    
    
    
    
    
    /************************ TEMPLATE STARTS HERE **********************/
    
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st     = null;
        solve();
        reader.close();
        writer.close();
    }
    
    static BufferedReader reader;
    static PrintWriter    writer;
    static StringTokenizer st;
    
    static String next()
    {while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}            
    st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
    static String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}             
    static int    nextInt()   {return Integer.parseInt(next());}
    static long   nextLong()  {return Long.parseLong(next());}     
    static double nextDouble(){return Double.parseDouble(next());}
    static char   nextChar()  {return next().charAt(0);}
    static int[]  nextIntArray(int n)         {int[] a= new int[n];   int i=0;while(i<n){a[i++]=nextInt();}  return a;}
    static long[] nextLongArray(int n)        {long[]a= new long[n];  int i=0;while(i<n){a[i++]=nextLong();} return a;}    
    static int[]  nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}            
    static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}            
    static void   print(Object o)  { writer.print(o);  }
    static void   println(Object o){ writer.println(o);}
    
    /************************ TEMPLATE ENDS HERE ************************/
    
}