Given is a string S of length N.

Find the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping.

More formally, find the maximum positive integer len such that there exist integers l_1 and l_2 ( 1 \leq l_1, l_2 \leq N - len + 1 ) that satisfy the following:

* l_1 + len \leq l_2

* S[l_1+i] = S[l_2+i] (i = 0, 1, ..., len - 1)




If there is no such integer len, print 0.

Constraints

* 2 \leq N \leq 5 \times 10^3
* |S| = N
* S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:


N
S


Output

Print the maximum length of a non-empty string that occurs twice or more in S as contiguous substrings without overlapping. If there is no such non-empty string, print 0 instead.

Examples

Input

5
ababa


Output

2


Input

2
xy


Output

0


Input

13
strangeorange


Output

5
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final String s = sc.next();
			
			String[] suffixs = new String[N];
			for(int i = 0; i < N; i++) {
				suffixs[i] = s.substring(i);
			}
			
			Arrays.sort(suffixs);
			
			int answer = 0;
			for(int i = 0; i < N - 1; i++) {
				final int curr = i;
				
				int lower = i + 1, upper = N;
				while(lower + 1 < upper) {
					final int middle = (lower + upper) / 2;
					
					if(suffixs[middle].startsWith(suffixs[curr])){
						lower = middle;
					}else {
						upper = middle;
					}
				}
				//System.out.println(suffixs[curr] + " " + suffixs[lower]);
				
				final int next = lower;
				
				final int curr_start_index = (N - suffixs[curr].length());
				final int next_start_index = (N - suffixs[next].length());
				final int start_index_diff = Math.abs(curr_start_index - next_start_index);
				
				//System.out.println(suffixs[curr] + " " + curr_start_index + " " + start_index_diff);
				
				int same = 0;
				while(same < suffixs[curr].length() && same < suffixs[next].length()){
					if(suffixs[curr].charAt(same) != suffixs[next].charAt(same)) { break; }
					if(same >= start_index_diff) { break; }
					
					same++;
				}
				
				answer = Math.max(same, answer);
			}
			
			System.out.println(answer);
			
			
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

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

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

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

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}