There are n banks in the city where Vasya lives, they are located in a circle, such that any two banks are neighbouring if their indices differ by no more than 1. Also, bank 1 and bank n are neighbours if n > 1. No bank is a neighbour of itself.

Vasya has an account in each bank. Its balance may be negative, meaning Vasya owes some money to this bank.

There is only one type of operations available: transfer some amount of money from any bank to account in any neighbouring bank. There are no restrictions on the size of the sum being transferred or balance requirements to perform this operation.

Vasya doesn't like to deal with large numbers, so he asks you to determine the minimum number of operations required to change the balance of each bank account to zero. It's guaranteed, that this is possible to achieve, that is, the total balance of Vasya in all banks is equal to zero.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of banks.

The second line contains n integers ai ( - 109 ≤ ai ≤ 109), the i-th of them is equal to the initial balance of the account in the i-th bank. It's guaranteed that the sum of all ai is equal to 0.

Output

Print the minimum number of operations required to change balance in each bank to zero.

Examples

Input

3
5 0 -5


Output

1


Input

4
-1 0 1 0


Output

2


Input

4
1 2 3 -6


Output

3

Note

In the first sample, Vasya may transfer 5 from the first bank to the third.

In the second sample, Vasya may first transfer 1 from the third bank to the second, and then 1 from the second to the first.

In the third sample, the following sequence provides the optimal answer: 

  1. transfer 1 from the first bank to the second bank; 
  2. transfer 3 from the second bank to the third; 
  3. transfer 6 from the third bank to the fourth. 
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.security.interfaces.DSAKey;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class a {

	public static class in {
		static BufferedReader reader;
		static StringTokenizer tokenizer;

		static void init(InputStream input) throws FileNotFoundException {
			// reader = new BufferedReader(new
			// FileReader("B-small-attempt4.in"));
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}

		static String next() throws IOException {
			while (!tokenizer.hasMoreTokens())
				tokenizer = new StringTokenizer(reader.readLine());
			return tokenizer.nextToken();
		}

		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		static double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
	}

	public static long comp(int n, int r) {
		r = Math.min(r, n - r);
		long ans = 1;
		for (int i = 1; i <= r; i++) {
			ans = ans * (long) (n - r + i) / (long) i;
		}
		return ans;

	}

	public static class node {

		int x;
		int y;
		int p;

		node(int x, int y, int p) {
			this.x = x;
			this.y = y;
			this.p = p;

		}

	}

	public static long gcd(int x, int y) {
		if (y == 0)
			return x;
		return gcd(y, x % y);
	}

	public static int tree[];

	public static void add(int idx, long val, int n, int tree[]) {

		while (idx <= n) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}

	public static int get(int idx) {
		int g = 0;
		while (idx > 0) {

			g += tree[idx];
			idx -= (idx & -idx);
		}

		return g;
	}

	public static class point implements Comparable<point> {
		int min;
		int a;
		int b;

		point(int min, int a, int b) {
			this.min = min;
			this.a = a;
			this.b = b;
		}

		@Override
		public int compareTo(point o) {
			if (o.min > min)
				return 1;
			else if (o.min < min)
				return -1;
			return 0;
		}
	}

	// for bad input
	static String ReadLn(int maxLg) {
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;
		String line = "";

		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null);
		return (new String(lin, 0, lg));
	}

	// IMPORT LIBRARY PACKAGES NEEDED BY YOUR PROGRAM
	// SOME CLASSES WITHIN A PACKAGE MAY BE RESTRICTED
	// DEFINE ANY CLASS AND METHOD NEEDED
	// LNode CLASS IS DEFINED BY DEFAULT
	// CLASS BEGINS, THIS CLASS IS REQUIRED

	public class LNode {
		public int value;
		public LNode next;

	}

	public static class ReverseLinkedList {
		// METHOD SIGNATURE BEGINS, THIS METHOD IS REQUIRED
		public static LNode reverseLinkedList(LNode list) {
			// INSERT YOUR CODE HERE
			int n = 0;
			LNode pointer = list;
			while (pointer != null) {
				n++;
				pointer = pointer.next;
			}

			int mid = (n + 1) / 2;
			if (n % 2 == 1)
				mid--;
			LNode arr[] = new LNode[n - mid];
			pointer = list;
			int p = 0;
			int c = 0;
			while (pointer != null) {

				if (c >= mid) {
					arr[p++] = pointer;
				}
				c++;
				pointer = pointer.next;
			}
			LNode swap = null;
			for (int i = 0; i < (n - mid) / 2; i++) {
				swap = arr[i];
				arr[i] = arr[n - mid - 1 - i];
				arr[n - mid - 1 - i] = swap;
			}

			pointer = list;
			p = 0;
			c = 0;
			while (pointer != null) {

				if (c >= mid - 1) {
					pointer.next = arr[p++];
				}
				c++;
				pointer = pointer.next;
			}

			return list;
		}
		// METHOD SIGNATURE ENDS
	}

	public static class points implements Comparable<points> {

		int dur;
		int idx;

		points(int d, int i) {
			dur = d;
			idx = i;
		}

		@Override
		public int compareTo(points o) {
			if (o.dur < dur)
				return 1;
			else if (o.dur > dur)
				return -1;
			else if (o.idx < idx)
				return 1;
			else
				return -1;

		}
	}

	public static void main(String[] args) throws IOException {
		// StringBuilder qq = new StringBuilder();
		in.init(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		HashMap<Long, Integer> mp = new HashMap();
		long sum = 0;
		int ans = n - 1;
		for (int i = 0; i < n; i++) {
			sum += (long) in.nextInt();
			int put = 1;
			if (mp.containsKey(sum))
				put += mp.get(sum);

			mp.put(sum, put);
			
			ans=Math.min(ans, n-put);

		}
		System.out.println(ans);

		out.close();

	}
}
